单源最短路径-贪心(Dijkstra (迪杰斯特拉),有向图，无向图)

问题描述

 给定一个图G = (V, E)，其中每条边的权是一个非负实数。另外给定顶点集合V中的一个顶点v，称为源。  问题：求从源v到所有其它各个顶点的最短路径。

问题分析

 单源最短路径问题的贪心选择策略：选择从源v出发，目前用最短的路径所到达的顶点，这就是目前的局部最优解。

基本思想

 设置一个集合S，初始时S中仅含有源v，然后不断地用贪心选择来扩充集合S ，即：从源v出发，选择用最短的路径所到达的顶点u，加入到集合S中，直至S包含所有V中顶点。

 把从源v到顶点u中间只经过S中顶点的路称为从源v到顶点u的特殊路径，用dist[u]来记录当前顶点u所对应的最短特殊路径长度。

 贪心选择：每次找到最小的dist[u]，将u添加到S中，同时对数组dist[]作必要的修改。

核心算法

例子

dist[w] := min(dist[w] , dist[u]+C[u ,w])

迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}- -10∞301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060

  prev[2]=1 prev[4]=1 prev[3]=4 prev[5]=3

 由数组dis[i]可知：从顶点1到顶点2、3、4、5的最短通路的长度分别为10、50、30和60。

 根据prev数组，源节点1到5的最短路径为：1，4，3，5

复杂度分析

Dijkstra 算法有两层循环，外层循环为n次，内层有两个循环：一个是选出最小的u(第5行)，另一个是修订disw。它们的次数都是n/2，所以内层循环的时间为O(n)。Dijkstra算法的时间复杂度为 O(n2)Dijkstra 算法能求出从源到其它各顶点的最短通路的长度，但是却并没有给出其最短通路。可借助prev数组得到。

完整代码

下面的代码是基于有向图的代码。若求无向图，在inPut()方法中打开Graph[pos2][pos1] = dis。

#include <bits/stdc++.h> using namespace std; const int max_ = 0x3f3f3f; int Graph[110][110]; int dist[110]; //dist[i]存储源到顶点 i 的当前最短路长度 int visited[110]; //标记i号顶点是否已并入S int pre[110]; //记录的是从源到顶点i的最短路径上i的前一个顶点。用来求出相应的最短路径 int m, n, p; //m代表路径的个数， n代表顶点的个数，p代表源 //回溯输出路径 void traceback(int i) { if(pre[i] == i) { printf("%d", i); } else { traceback(pre[i]); printf(" %d", i); } } void outPut() { for(int i = 1; i <= n; ++i) { if(i != p) { printf("点 %d 到点 %d 的最小距离为 %d\n", p, i, dist[i]); cout << "路径为 :" << endl; traceback(i); cout << endl; } } } void Dijkstra() { //初始化 for(int i = 1; i <= n; ++i) { dist[i] = Graph[p][i]; visited[i] = 0; pre[i] = p; } dist[p] = 0; visited[p] = 1; for(int i = 1; i < n; ++i) { int pos, min_len = max_; for(int i = 1; i <= n; ++i) { if(!visited[i] && min_len > dist[i]) { pos = i, min_len = dist[i]; } } visited[pos] = 1; for(int j = 1; j <= n; ++j) { if(!visited[j] && dist[j] > min_len + Graph[pos][j]) { dist[j] = min_len + Graph[pos][j]; pre[j] = pos; } else continue; } } } void inPut() { int pos1, pos2, dis; memset(Graph, max_, sizeof(Graph)); scanf("%d %d %d", &p, &n, &m); // cout << "p = " << p << " n = " << n << " m = " << m << endl; for(int i = 1; i <= m; ++i) { scanf("%d %d %d", &pos1, &pos2, &dis); Graph[pos1][pos2] = dis; //Graph[pos2][pos1] = dis;//若图是无向图，则打开此代码 } } int main() { inPut(); Dijkstra(); outPut(); }

测试用例

测试无向图

输入 1 5 7 1 2 10 1 4 30 1 5 100 2 3 50 4 5 60 3 5 10 3 4 20

输出 点 1 到点 2 的最小距离为 10 路径为 : 1 2 点 1 到点 3 的最小距离为 50 路径为 : 1 4 3 点 1 到点 4 的最小距离为 30 路径为 : 1 4 点 1 到点 5 的最小距离为 60 路径为 : 1 4 3 5

测试有向图

输入 1 5 7 1 2 10 1 5 100 1 4 30 2 3 50 3 5 10 4 3 20 4 5 60

输出 点 1 到点 2 的最小距离为 10 路径为 : 1 2 点 1 到点 3 的最小距离为 50 路径为 : 1 4 3 点 1 到点 4 的最小距离为 30 路径为 : 1 4 点 1 到点 5 的最小距离为 60 路径为 : 1 4 3 5