DAG图上指定单源, 求其到其他各个顶点的最短距离

缘起

问题: 给定一个dag网, 然后给定上面的一个顶点, 要求它到其他顶点的最短距离.

分析

有向网（无向网）的最短距离我们自然想到了的是dijkstra、floyd、bellman-ford 等算法, 但是即便堆优化, 也不是线性的算法, 而至多是 O(nlogn)的. 而且依据CBA理论（【1】）知道这是这三种算法的性能极限. 但是有没有更好的算法呢? 注意，图是dag，可以拓扑排序. 我们在关键路径中其实用过类似的思想——dp+拓扑排序（【2】）.

其中dp的模型是

1
dp[i] = min {dp[j] + <j,i>}, 其中j 的取值范围是弧 <j,i>存在

这一算法是线性的算法. 其本质是因为上述dp模型的成立. 对于一般有向图而言, 因为可能存在环（即便不是负权环）, 所以存在循环依赖, 所以上述公式未必成立. 所以即便dijkstra算法也是求有向非负权网的单源最短路径, 但是性能也只能到 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <stack>
#pragma warning(disable:4996)

#define LOCAL
using namespace std;

const int MAX_N = 105;
const int INF = 0x3f3f3f3f;

struct Edge
{
	int v,w; // v是终点, w是权(本例中, 权可以是负数， 因为基于的是dp)
	Edge(int v, int w):v(v),w(w){}
};

typedef vector<Edge>::iterator it;


struct DAG
{
	
	int n; // 顶点的实际个数
	vector<Edge> vertex[MAX_N]; // 边
	int source; // 单源
	int dp[MAX_N]; // dp[i] 表示单源到i的最短路径
	int broker[MAX_N];// 掮客,broker[i] = j 表示是j将i拉入伙的
	int indeg[MAX_N]; // 拓扑排序用的入度域
	stack<int> s; // 拓扑排序用的栈

	DAG()
	{
		memset(dp, 0x3f, sizeof(dp)); // 默认都是无穷大
		memset(indeg, 0, sizeof(indeg));
		puts("输入顶点的个数");
		scanf("%d", &n);
		puts("输入单源");
		scanf("%d", &source);
		dp[source]=  0; // 单源到它自己的最短路径自然是0
		for (int i = 0; i<n; i++) broker[i] = source; // 伊始默认都是source将其拉入伙的
		puts("输入弧的起点终点和权重");
		int start, end, weight;
		while(~scanf("%d%d%d", &start, &end, &weight))
		{
			vertex[start].push_back(Edge(end, weight));
			indeg[end]++;
		}
		for (int i = 0; i<n; i++) if (!indeg[i]) s.push(i); // 初始化栈
	}

	void shortestpath()  // dag图单源最短路径
	{
		while(!s.empty())
		{
			int t = s.top();
			s.pop();
			for (it x = vertex[t].begin(); x!=vertex[t].end(); x++)
			{
				if (!--indeg[x->v]) s.push(x->v);
				if (dp[x->v] > dp[t]+x->w)
				{
					dp[x->v] = dp[t]+x->w;
					broker[x->v] = t; // 掮客变了
				}
			}
		}
		for (int i = 0; i<n;i++)
		{
			if (dp[i]<INF)
			{
				printf("单源%d到%d的最短路径是%d: ", source, i, dp[i]);
				printpath(i);
			}
			else
			{
				printf("单源%d无法到达%d.", source, i);
			}
			puts("");
		}
	}

private:
	void printpath(int i)
	{
		if (i==source)
		{
			printf("%d -> ",source);
			return;
		}
		printpath(broker[i]);
		printf("%d -> ",i);
	}
};


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	DAG g;
	g.shortestpath();
	return 0;
}
/*
测试数据
9 0
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
*/

参考

【1】https://yfsyfs.github.io/2019/05/25/CBA%E7%90%86%E8%AE%BA-%E4%B8%BA%E4%BB%80%E4%B9%88%E5%9F%BA%E4%BA%8E%E6%AF%94%E8%BE%83%E7%9A%84%E6%8E%92%E5%BA%8F%E6%96%B9%E6%B3%95%E7%9A%84%E6%80%A7%E8%83%BD%E6%9E%81%E9%99%90%E6%98%AFO-nlogn/

【2】https://yfsyfs.github.io/2019/05/21/%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84/