7,129
个编辑
更改
跳到导航
跳到搜索
第75行：
第75行： − + − Several algorithms exist to find [[Shortest path problem|shortest]] and [[Longest path problem|longest]] paths in graphs, with the important distinction that the former problem is computationally much easier than the latter.+ − − Several algorithms exist to find shortest and longest paths in graphs, with the important distinction that the former problem is computationally much easier than the latter. − − 求解图的[[最短路径]]和[[最长路径]]的均有多种算法，但是前者的计算比后者简单得多。 + − + − [[Dijkstra's algorithm]] produces a list of shortest paths from a source vertex to every other vertex in directed and undirected graphs with non-negative edge weights (or no edge weights), whilst the [[Bellman–Ford algorithm]] can be applied to directed graphs with negative edge weights. The [[Floyd–Warshall algorithm]] can be used to find the shortest paths between all pairs of vertices in weighted directed graphs. − − Dijkstra's algorithm produces a list of shortest paths from a source vertex to every other vertex in directed and undirected graphs with non-negative edge weights (or no edge weights), whilst the Bellman–Ford algorithm can be applied to directed graphs with negative edge weights. The Floyd–Warshall algorithm can be used to find the shortest paths between all pairs of vertices in weighted directed graphs. − − '''<font color="#ff8000">Dijkstra 算法</font>'''产生了一个从源顶点到无向或有向图中每个顶点的最短路径列表，而'''<font color="#ff8000">Bellman-Ford 算法</font>''' 可以应用于具有负边权重的有向图。利用'''<font color="#ff8000"> Floyd-Warshall 算法</font>'''可以求出加权有向图中所有顶点对之间的最短路径。
→路径寻找 Finding paths
<br>
<br>
== 路径寻找 Finding paths==
== 路径寻找==
求解图的最短和最长路径有多种算法，但是前者的计算比后者简单得多。
'''<font color="#ff8000">Dijkstra 算法</font>'''产生了一个从源顶点到无向或有向图中每个顶点的最短路径列表，而'''<font color="#ff8000">Bellman-Ford 算法</font>''' 可以应用于具有负边权重的有向图。利用'''<font color="#ff8000"> Floyd-Warshall 算法</font>'''可以求出加权有向图中所有顶点对之间的最短路径。
<br>
== 参见==
== 参见==