有向无环图中的单源最短路径

2025 年 1 月 12 日 | 9 分钟阅读

简介

在图论中，单源最短路径 (SSSP) 问题是指在有向图中找到从单个源顶点到所有其他顶点的最短路径。当处理有向无环图 (DAG) 时，问题变得更容易处理，因为没有环路简化了解决方案。

有向无环图 (DAG)：一种不包含任何环路的有向图，这意味着不存在一系列顶点使得第一个和最后一个顶点相同，并且所有边都具有指定方向。

有向无环图 (DAG) 中的单源最短路径介绍

最优性原理：解决 DAG 中 SSSP 问题的关键在于拓扑排序的存在。拓扑排序是图的顶点的线性排序，使得对于每个有向边 (u, v)，顶点 u 在排序中位于 v 之前。DAG 通常至少有一个拓扑排序。
拓扑排序：给定一个 DAG，计算其顶点的拓扑排序。这可以使用深度优先搜索 (DFS) 等算法高效完成。
算法概述：将从给定顶点到所有其他顶点的距离初始化为无穷大，除了源本身，它设置为 0。按拓扑顺序处理顶点。对于拓扑顺序中的每个顶点 u，放松（更新）其相邻顶点的距离。
松弛：对于与 u 相邻的每个顶点 v，如果通过 u 到 v 的距离比当前已知的到 v 的距离短，则更新到 v 的距离。

Single Source Shortest Path in a directed Acyclic Graphs

历史

有向无环图最短路径算法的历史与图论和算法优化的发展密切相关。以下是简要的历史概述：

Dijkstra 算法 (1956)：Edsger Dijkstra 提出了著名的 Dijkstra 算法来查找图中两个节点之间的最短路径。然而，Dijkstra 算法假设非负权重，不能直接应用于具有负权重或周期的图。
拓扑排序（早期实现）：拓扑排序的概念对于解决问题至关重要，可以追溯到图论的早期。众所周知，有向无环图 (DAG) 的拓扑排序存在并且可以高效计算。
动态规划 (1960s)：动态规划原理在 DAG 中 SSSP 问题中的应用出现。其思想是递归地计算最短路径，给定任务的最优子结构。
Bellman-Ford 算法 (1958)：Richard Bellman 引入了 Bellman-Ford 算法，这是一种多功能算法，可以处理图中的负权重（但不能处理负周期）。虽然 Bellman-Ford 可以用于 SSSP，但其时间复杂度高于 DAG。
DAG 中高效 SSSP（自 1980 年代）：研究人员专注于开发专门为 DAG 优化的更高效算法。关键在于，在 DAG 中，拓扑排序可以用于以线性时间计算最短路径。
Yen 算法 (1971)：Satoru Yen 提出了一种在 DAG 中查找最短路径的算法。他的算法基于拓扑排序，可以处理负权重的图。
现代进展（21 世纪以来）：正在进行的研究继续改进和优化 DAG 的 SSSP 算法。添加了先进的技术和数据结构，以实现更好的时间和空间复杂度。
在各个领域的应用：DAG 的 SSSP 问题在项目管理、网络路由和编译器优化等各个领域都有应用。随着技术和计算方法的发展，更复杂的算法不断被开发。如今，DAG 的 SSSP 算法已经成熟，属于图算法的标准集。它们用于各种实际场景，其中底层系统可以建模为有向无环图。

伪代码

function dagShortestPath(Graph G, Vertex source):
    // Step 1: Topological ordering
    topOrder = topologicalSort(G)
    
    // Step 2: Initialize distances
    dist = [infinity, infinity, ..., infinity]
    dist[source] = 0
    
    // Step 3: Process vertices in topological order
    for each vertex u in topOrder:
        // Step 4: Relaxation
        for each vertex v adjacent to u:
            if dist[u] + weight (u, v) < dist[v]:
                dist[v] = dist[u] + weight (u, v)

时间复杂度：拓扑排序需要 O(V + E) 时间。松弛阶段需要 O(E) 时间，因为每条边只处理一次。因此，总时间复杂度为 O(V + E)。
示例：考虑一个有顶点 A、B、C、D、E 和边 (A, B)、(A, C)、(B, D)、(C, D)、(D, E) 的 DAG。如果 A 是源点，算法会计算到 B、C、D 和 E 的最短路径。通过利用图的无环性，SSSP 问题可以在 DAG 中高效解决，为在某些场景中查找最短路径提供了一个优雅的解决方案。

有向无环图中单源最短路径的 C++ 实现

#include <iostream>
#include <list>
#include <stack>
#include <vector>
#include <limits>

using namespace std;

// Class to represent a graph
class Graph {
    int V; // Number of vertices
    list<pair<int, int>>* adj; // Adjacency list

public:
    Graph(int V);

    void addEdge(int u, int v, int weight);

    void topologicalSortUtil(int v, vector<bool>& visited, stack<int>& stack);

    vector<int> dagShortestPath(int src);
};

// Constructor
Graph::Graph(int V) {
    this->V = V;
    adj = new list<pair<int, int>>[V];
}

// Add an edge to the graph
void Graph::addEdge(int u, int v, int weight) {
    adj[u].push_back(make_pair(v, weight));
}

// A recursive function used by topologicalSort
void Graph::topologicalSortUtil(int v, vector<bool>& visited, stack<int>& stack) {
    visited[v] = true;

    for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
        if (!visited[i->first])
            topologicalSortUtil(i->first, visited, stack);
    }

    stack.push(v);
}

// Function that returns a vector containing the shortest distances from source to all other vertices
vector<int> Graph::dagShortestPath(int src) {
    vector<int> dist(V, numeric_limits<int>::max());
    stack<int> stack;

    // Mark all the vertices as not visited
    vector<bool> visited(V, false);

    // Call the recursive helper function to store Topological Sort starting from source vertex
    for (int i = 0; i < V; ++i)
        if (!visited[i])
            topologicalSortUtil(i, visited, stack);

    // Initialize the distance to the source vertex as 0
    dist[src] = 0;

    // Process vertices in topological order
    while (!stack.empty()) {
        int u = stack.top();
        stack.pop();

        // Update dist value of the adjacent vertices of the popped vertex
        for (auto i = adj[u].begin(); i != adj[u].end(); ++i)
            if (dist[u] != numeric_limits<int>::max() && dist[u] + i->second < dist[i->first])
                dist[i->first] = dist[u] + i->second;
    }

    return dist;
}

// Driver program to test the above functions
int main() {
    // Create a graph given in the example
    Graph g(6);
    g.addEdge(0, 1, 5);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 3, 6);
    g.addEdge(1, 2, 2);
    g.addEdge(2, 4, 4);
    g.addEdge(2, 5, 2);
    g.addEdge(2, 3, 7);
    g.addEdge(3, 5, 1);
    g.addEdge(3, 4, -1);
    g.addEdge(4, 5, -2);

    int source = 1;

    vector<int> dist = g.dagShortestPath(source);

    // Print the calculated shortest distances
    cout << "Shortest distances from source " << source << ":\n";
    for (int i = 0; i < dist.size(); i++)
        cout << "Vertex " << i << ": " << dist[i] << endl;

    return 0;
}

示例输出

Shortest distances from source 1:
Vertex 0: 9223372036854775807   // Infinity, as not reachable from source 1
Vertex 1: 0
Vertex 2: 2
Vertex 3: 6
Vertex 4: 4
Vertex 5: 7

说明

图表示：程序使用邻接表来表示有向图。图类具有添加边 (addEdge) 和拓扑排序 (topologicalSortUtil) 的方法。
拓扑排序：topologicalSortUtil 函数使用 DFS 搜索执行拓扑排序。结果存储在栈上。
DAG 最短路径算法：dagShortestPath 函数实现了 DAG 最短路径算法。它将所有点的距离 (dist) 重置为正无穷大，除了起点，它设置为 0。然后它按拓扑顺序处理顶点，并根据松弛程度更新距离。
主函数：在主函数中，使用 Graph 类创建了一个示例有向无环图。起始顶点设置为 1。调用 dagShortestPath 函数来计算从起始点到所有其他顶点之间的最短距离。然后打印计算出的距离。

有向无环图中单源最短路径的属性

在有向无环图 (DAG) 中，单源最短路径问题 (SSPP) 是指在图中找到从一个起点到所有其他点的最短路径。由于 DAG 中没有环路，因此与一般循环图相比，某些属性使 SSSP 问题更高效。以下是一些重要特征：

拓扑排序：DAG 可以拓扑排序，即顶点可以线性排序，使得在每个有向边 (u, v) 中，顶点 u 在排序中位于 v 之前。此属性对于 DAG 的高效 SSSP 算法至关重要。
最优子结构：DAG 中的 SSSP 问题具有最优子结构属性。从源到某个顶点 v 的最短路径由到某个顶点 u 的最短路径以及一条边 (u, v) 组成。这允许使用动态规划。
动态规划解决方案：由于最优基础设施属性，动态规划可以用于高效解决 DAG 中的 SSSP 问题。问题可以分解成更小的子问题，并且这些子问题的解决方案可以存储和重用。
松弛过程：松弛操作是许多最短路径算法中的关键步骤，在 DAG 中可以简化。如果在松弛阶段，通过顶点 u 可以缩短到顶点 v 的距离，这意味着从源到 u 的距离已经是最优的。这是拓扑排序的结果。没有负环：根据定义，DAG 不包含环。因此，图中没有负环。这意味着每对点的最短路径都是明确定义和有界的。
线性时间复杂度：基于拓扑排序的算法，例如受动态规划启发的算法，可以实现 O(V + E) 的线性时间复杂度（V 为顶点数，E 为边数）来解决 DAG 上的 SP 问题。
Bellman-Ford 算法：尽管 Bellman-Ford 算法是为循环图设计的，但它也可以用于解决 DAG 中的 SSSP 问题。总之，DAG 的无环性允许使用拓扑排序和最优子结构等属性来解决单源最短路径问题，从而实现更高效的算法。

有向无环图中单源最短路径的复杂度

在有向无环图 (DAG) 中查找单源最短路径的时间复杂度可以在线性时间内实现，即 O(V + E)，其中 V 是顶点数，E 是边数。有效的时间复杂度主要归因于 DAG 顶点的拓扑排序。拓扑排序需要 O(V + E) 时间，然后按拓扑顺序松弛边也需要 O(V + E) 时间。因此，使用拓扑排序方法在 DAG 中查找 SSSP 的总时间复杂度为 O(V + E)。用于解决 DAG 中 SSSP 的流行算法包括拓扑排序和松弛方法，以及类似 Bellman-Ford 的算法，尽管它们是为循环图设计的。在 DAG 的情况下，由于没有环路，这些算法也能在线性时间内工作。值得注意的是，这些时间复杂度假设图是以邻接表的形式给出的，这是稀疏图的常见表示。如果图是稠密的并表示为邻接矩阵，则时间复杂度可能会有所不同。

结论

有向无环图 (DAG) 由于没有环路，因此对单源最短路径 (SSSP) 问题具有独特且高效的解决方案。

最优性：DAG 没有环路，这消除了负权重环的可能性。- 因此，从起点到其他某个顶点的最短路径是明确定义的，并且可以通过顶点的拓扑顺序来确定。
拓扑排序：在 DAG 上使用任何特殊的 SSSP 算法之前，顶点的拓扑排序至关重要。- 拓扑排序确保顶点按正确顺序处理，从而可以顺序计算最短路径。
算法方法：用于解决 DAG 中 SSSP 问题的一种常用算法是动态规划。该算法按拓扑顺序迭代顶点，根据其传入边更新每个顶点的最短路径估计。
时间复杂度：在 DAG 中查找单源最短路径的时间复杂度通常是线性的，通常为 O(V + E)，其中 V 是顶点数，E 是边数。线性时间复杂度来自拓扑排序的线性时间复杂度和每次边迭代。
空间复杂度：空间复杂度通常由用于存储中间结果和拓扑顺序的数据结构决定。- 它通常是 O(V + E) 或 O(V)，具体取决于所使用的特定算法。
应用：DAG 中的 SSSP 在各个领域都有应用，例如项目调度、关键路径分析和网络路由，其中底层结构可以建模为 DAG。

总之，利用有向无环图的无环性质可以高效解决单源最短路径问题。没有环路简化了算法方法，使得可以线性时间计算最短路径。此功能使 DAG 成为表示和解决有向网络或工作流中的路由优化问题的合适模型。

下一主题所有对最短路径

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

关注我们

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

DAA 教程

渐进分析

复发

排序分析

分而治之

排序

下界理论

线性时间排序

哈希

二叉搜索树

红黑树

动态规划

贪婪算法

回溯

最小生成树

最短路径

所有对最短路径

最大流

排序网络

复杂度理论

近似算法

字符串匹配

面试题

其他

有向无环图中的单源最短路径

简介

历史

伪代码

有向无环图中单源最短路径的 C++ 实现

有向无环图中单源最短路径的属性

有向无环图中单源最短路径的复杂度

结论

相关帖子

负权重边

Bellman-Ford 算法

单源最短路径

表示最短路径

Dijkstra 算法

松弛

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器