使用有向图实现最短路径算法的最佳方法 [英] Best way to implement shortest path algorithm with directed graph

问题描述

让我们假设我有一个带有边的带权无向图，并希望找到最短路径以及我可以从起点到终点的所有可能路径以及距离，那么实现它的最佳方法是什么？广度深度搜索和k路径算法似乎提供了合理的解决方案，虽然我不知道哪一个是最好的解决方案

对不起，不能发表评论...

如果你需要所有可能的路径，你不可能比树遍历更好（比如BFS或DFS）。请注意，您需要考虑每个节点的次数，因为它可以从一开始就达到（树比原始图大得多 - 如果图中有周期，则无限大，但是让我们假设您不' t）。

要获得最小的路径，最后可以在列表中查找它;或者最好是，你可以使用类似Dijkstra的顺序来遍历树，所以最短路径将是第一个出现。

Lets assume i have a weighted undirected graph with edges and wanted to find the shortest path as well as all possible paths that i could follow from the startpoint to the endpoint with distances, what would be the best way to implement this? Breadth depth search and k paths algorithm seem to offer reasonable solutions, although im not sure which is best

解决方案

Sorry, can't post this as comments...

If you need all possible paths, you can't do really better than "tree" traversal (BFS or DFS for instance). Note that you'll need to consider each node as many times as it can be reached from the start (the "tree" is much bigger than the original graph - even infinite if you have cycles in your graph, but let's assume you don't).

To get the smallest path, you could look for it in your list in the end; or preferably, you could use a Dijkstra-like order for your tree traversal, so the shortest path will be the first to come up.

这篇关于使用有向图实现最短路径算法的最佳方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！