So che l'algoritmo di Bellman-Ford funziona per i grafici diretti ma solo per Info voglio sapere se funzionerà per il grafico Un-directed? Poiché con il grafico Un-directed non sarà in grado di rilevare cicli perché i bordi paralleli saranno considerati come Cicli !!. Si prega di precisare.È possibile applicare l'algoritmo di Bellman ford a Undirected Graph
risposta
In effetti qualsiasi grafico non orientato è anche un grafico diretto.
Devi solo specificare i bordi {u, v} due volte (u, v) e (v, u).
Ma non dimenticare che questo significa anche che qualsiasi spigolo con un peso negativo conterà come un loop. Poiché l'algoritmo di Bellman-Ford funziona SOLO su grafici che non contengono cicli con pesi negativi, ciò significa in realtà che il grafico non diretto non deve contenere bordi con peso negativo.
Se non è abbastanza bello usare Bellmann-Ford.
Per elaborare questo - poiché il grafico deve avere solo bordi non negativi, ciò significa che potresti voler semplicemente utilizzare l'algoritmo di Dijkstra, poiché è asintoticamente più veloce. – templatetypedef
Ho lo stesso dubbio. Grazie per il chiarimento. – whitehat
Dai un'occhiata a [questo] (http://stackoverflow.com/questions/14538403/shortest-path-algorithms-for-undirected-graph) uno. – Nik