7,129
个编辑
更改
跳到导航
跳到搜索
第216行：
第216行： + + + +
→Path algorithms
=== Path algorithms ===
=== Path algorithms ===
Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find [[shortest path]]s and [[longest path problem|longest paths]] from a given starting vertex in DAGs in linear time by [[Topological sorting#Application to shortest path finding|processing the vertices in a topological order]], and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges.<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref> In contrast, for arbitrary graphs the shortest path may require slower algorithms such as [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]],<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> and longest paths in arbitrary graphs are [[NP-hard]] to find.<ref>Cormen et al. 2001, p. 966.</ref>
Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find [[shortest path]]s and [[longest path problem|longest paths]] from a given starting vertex in DAGs in linear time by [[Topological sorting#Application to shortest path finding|processing the vertices in a topological order]], and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges.<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref> In contrast, for arbitrary graphs the shortest path may require slower algorithms such as [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]],<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> and longest paths in arbitrary graphs are [[NP-hard]] to find.<ref>Cormen et al. 2001, p. 966.</ref>
Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find shortest paths and longest paths from a given starting vertex in DAGs in linear time by processing the vertices in a topological order, and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges. In contrast, for arbitrary graphs the shortest path may require slower algorithms such as Dijkstra's algorithm or the Bellman–Ford algorithm, and longest paths in arbitrary graphs are NP-hard to find.
基于拓扑排序原理，有些算法用在 DAGs 上代替一般图时变得更简单。例如，通过处理拓扑有序中的顶点，并计算每个顶点的路径长度为通过任一传入边得到的最小或最大长度，可以在线性时间内从给定的 DAGs 顶点找到最短路径和最长路径。相反，对于任意图，最短路径可能需要较慢的算法，如 Dijkstra 算法或 Bellman-Ford 算法，而任意图中的最长路径是 np 难以找到的。
== Computational problems ==
== Computational problems ==