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
- 1. Implementazione dell'algoritmo Bellman-Ford C++
- 2. Bellman Ford e One Olympiad Questions?
- 3. differenza tra l'algoritmo di Bellman Ford e Dijkstra
- 4. È possibile applicare la partizione a `a -> IO Bool`?
- 5. È possibile applicare il bootstrap solo a div, usando CDN?
- 6. È possibile applicare __restrict__ a shared_ptr <T>?
- 7. È possibile applicare panel.resize nel pannello stesso
- 8. Errore di sincronizzazione applink Ford
- 9. è possibile applicare PCA su qualsiasi classificazione di testo?
- 10. È possibile applicare una funzione generica su elementi di tupla?
- 11. Ford CAN Data e ELM327
- 12. È possibile applicare JavaScript come metodo nell'obiettivo-c?
- 13. accelera le richieste Ajax - è possibile applicare la compressione gzip?
- 14. È possibile applicare un metodo generico a un elenco di elementi?
- 15. È possibile applicare una trasformazione "twist & squeeze" a un intero documento HTML?
- 16. In automapper è possibile applicare lo stesso valore resolver a più membri
- 17. Flusso massimo - Ford-Fulkerson: grafico indiretto
- 18. Applicare proprietà a più oggetti
- 19. office365 microsoft graph Ricerca a testo completo
- 20. Postare su Facebook Graph Api è lento
- 21. Tuple splat/applicare a Rust
- 22. È sicuro passare 'argomenti' di 'applicare()'
- 23. Applicare trasformazioni di matrice a BoundingBox
- 24. È possibile applicare l'autenticazione di base/il middleware nei percorsi con una whitelist in Express?
- 25. Perché non è possibile applicare @SafeVarags ai metodi di istanza in una classe finale?
- 26. F # quotations object graph
- 27. In che modo è possibile applicare gli errori di convalida Django con Bootstrap?
- 28. È possibile applicare due trasformazioni di pattern corrispondenti in un'unica operazione?
- 29. Facebook Graph API: Get data di joinin
- 30. Applicare lo stesso stile a più elementi
Dai un'occhiata a [questo] (http://stackoverflow.com/questions/14538403/shortest-path-algorithms-for-undirected-graph) uno. – Nik