Bellman-Ford

import heapq as hq
import math
from random import *
import networkx as nx
INF = float("inf")

def generarGrafoConPesos(n,m):
    mat = [[] for i in range(n)]
    for j in range(m):
        v1 = randint(0, n - 1)
        v2 = randint(0, n - 1)
        w = randint(1, 10)
        adyacentes = [x[0] for x in mat[v1]]
        adyacentes2 = [x[0] for x in mat[v2]]
        while(v2 in adyacentes or v2 == v1 or v1 in adyacentes2):
            v1 = randint(0, n - 1)
            v2 = randint(0, n - 1)
        mat[v1] += [(v2,w)]
    return mat

def dibujarGrafoConPesos(lista):
    G = nx.DiGraph()
    for i in range(len(g)):
        G.add_node(i)
    for v1 in range(len(lista)):
        for v2 in lista[v1]:
            G.add_edge(v1, v2[0],weight=v2[1])
    nx.draw_circular(G, with_labels=True, font_weight='bold', node_size=500)
    labels = nx.get_edge_attributes(G,'weight')
    nx.draw_networkx_edge_labels(G,pos=nx.circular_layout(G),edge_labels=labels)
g = generarGrafoConPesos(10,28)

print(g)
dibujarGrafoConPesos(g)

def BellmanFord(g, inicio):
    distancia = [INF] * len(g)
    predecesor = [(-1,-1)] * len(g)

    distancia[inicio] = 0
    for i in range(len(g) - 1):
        for u in range(len(g)):
            for v,w in g[u]:
                if distancia[u] != INF and distancia[u] + w < distancia[v]:
                    distancia[v] = distancia[u] + w
                    predecesor[v] = (u,w)
    return distancia, predecesor

BellmanFord(g, 0)

def hacerRecorridosBellmanFord(g,inicio):
    d, p = BellmanFord(g, inicio)
    recorrido = []
    for u in range(len(p)):
        if p[u][0] > -1:
            recorrido += [(p[u][0],u,p[u][1])]
    return recorrido

hacerRecorridosBellmanFord(g,0)

#opcional
def dibujarRecorrido(g,recorrido):
    G = nx.DiGraph()
    for i in range(len(g)):
        G.add_node(i)
    for x in recorrido:
        G.add_edge(x[0], x[1], weight = x[2])
    nx.draw_circular(G, with_labels=True, font_weight='bold', node_size=500)
    labels = nx.get_edge_attributes(G,'weight')
    nx.draw_networkx_edge_labels(G,pos=nx.circular_layout(G),label_pos=0.3,edge_labels=labels)

dibujarRecorrido(g, hacerRecorridosBellmanFord(g,0))