Algoritmo di Belman Kalaba spiegato - algoritmo grafico

C'è una differenza tra Belman-Ford e questo?

Qualcuno può spiegare come implementarloper trovare il percorso più lungo tra i nodi dati? So che l'algoritmo calcola il percorso più breve tra due nodi, quindi se qualcuno può spiegare come implementarlo posso capire come modificarlo per darmi il percorso più lungo.

risposte:

Risponderò nel caso in cui qualcun altro avrà la stessa domanda in futuro.

Ho trovato un'implementazione Python (purtroppo non è documentata e sto ancora giocando con essa cercando di capirlo appieno).

Questo calcola il percorso più breve tra un dato nodo e tutti gli altri nodi nel grafico.

from json.encoder import INFINITY
def BellmanKalaba(v,x,m):
L=list()
iteration=list()
for j in range(len(v)):
iteration.append(v[x][j])
L.append(iteration)
k=0
while True:
iteration=[0 for i in range(len(v))]
for j in range(len(v)):
minim=INFINITY
for i in range(1,len(v)):
a=L[len(L)-1][i]+v[i][j]
if a < min:
minim=a
iteration[j]=minim
k+=1
L.append(iteration)
if iteration==L[len(L)-1]:
return L
if k==m:
return 0

v è una matrice che rappresenta un grafico ponderato, x è il nodo di partenza, m è il numero di bordi.

Ora, questo diventa un po 'più strano perché L in realtà contiene 2 liste, quindi il percorso più breve da x a y sarà min(L[0][y], L[1][y]). Non posso spiegare esattamente come funziona. Inoltre, questo non funziona per nessun dato grafico.

È un inizio, forse ora qualcuno può entrare e aiutare.