更改

跳到导航 跳到搜索
添加4字节 、 2021年6月14日 (一) 12:01
无编辑摘要
第128行: 第128行:     
===最短或最长路径问题===
 
===最短或最长路径问题===
基于拓扑排序的性质,有向无环图的[[最短路问题 Shortest paths]]和[[最长路径问题 Longest paths]]可以在线性时间内解决。将顶点拓扑排序后,从前到后遍历每一个顶点,对于遍历到的顶点,更新其所有出边所到达顶点的长度值。如果求最短路,则在本边是更短路径的一部分时更新。求最长路则反之。<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref>对于非有向无环图,最短路需要用复杂度为<math>O(|E|+|V|\log|V|)</math>的<font color="#ff8000"> '''戴克斯特拉算法 Dijkstra's algorithm''' </font>或<math>O (|V| |E|)</math>的<font color="#ff8000"> '''贝尔曼-福特算法 Bellman–Ford algorithm''' </font>等。<ref>Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</ref>最长路径则是一个[[NP困难|NP困难问题]]。<ref>Cormen et al. 2001, p. 966.</ref>
+
基于拓扑排序的性质,有向无环图的[[最短路问题 Shortest paths]]和[[最长路径问题 Longest paths]]可以在线性时间内解决。将顶点拓扑排序后,从前到后遍历每一个顶点,对于遍历到的顶点,更新其所有出边所到达顶点的长度值。如果求最短路,则在本边是更短路径的一部分时更新。求最长路则反之。<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref>对于非有向无环图,最短路需要用复杂度为<math>O(|E|+|V|\log|V|)</math>的<font color="#ff8000"> '''戴克斯特拉算法 Dijkstra's algorithm''' </font>或<math>O (|V| |E|)</math>的<font color="#ff8000"> '''贝尔曼-福特算法 Bellman–Ford algorithm''' </font>等。<ref>Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</ref>最长路径则是一个[[NP-难问题|NP困难问题]]。<ref>Cormen et al. 2001, p. 966.</ref>
    
<br>
 
<br>
7,129

个编辑

导航菜单