给定一个有向图，其边的权重为 -ve 或 +ve，找到从顶点 s 到顶点 d 的所有路径中权重最小的边的算法是什么？
最佳答案
来自 Wikipedia
您描述的是单一来源最短路径问题。如果边缘仅是正数，则可以使用 Dijkstra 解决；如果边缘也允许为负数，则可以使用 Bellman-Ford 来解决。
The most important algorithms for solving this problem are:
- Dijkstra's algorithm solves the single-source shortest path problem.
- Bellman–Ford algorithm solves the single-source problem if edge weights may be negative.
- A* search algorithm solves for single pair shortest path using heuristics to try to speed up the search.
- Floyd–Warshall algorithm solves all pairs shortest paths.
- Johnson's algorithm solves all pairs shortest paths, and may be faster than Floyd–Warshall on sparse graphs.
- Viterbi algorithm solves the shortest stochastic path problem with an additional probabilistic weight on each node.
关于algorithm - 有向图所有路径中的最小权重边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47251811/