迪杰斯特拉算法详解+模版+例题

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。——百度百科

基本思想：

通过Dijkstra计算图G中的最短路径时，需要指定起点vs(即从顶点vs开始计算)。
此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点，而U则是记录还未求出最短路径的顶点(以及该顶点到起点vs的距离)。
初始时，S中只有起点vs；U中是除vs之外的顶点，并且U中顶点的路径是"起点vs到该顶点的路径"。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

操作步骤：

(1) 初始时，S只包含起点vs；U包含除vs外的其他顶点，且U中顶点的距离为"起点vs到该顶点的距离"[例如，U中顶点v的距离为(vs,v)的长度，然后vs和v不相邻，则v的距离为∞]。

(2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。

(3) 更新U中各个顶点到起点vs的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(vs,v)的距离可能大于(vs,k)+(k,v)的距离。

(4) 重复步骤(2)和(3)，直到遍历完所有顶点。
在这里插入图片描述
上述内容摘自：添加链接描述

模板:

int dist[510];//dist[i]存储S到i结点的最短距离
int book[510];//标记i结点是否访问
int v[510][510];//存储图信息

//主要思想一个大循环+两个小循环
void dijkstra(){int u, minx;book[S] = 1;for(int i = 0; i < N; i++){//dist[]数组初始化，把起始结点S到i结点的距离赋值给diat[i]dist[i] = v[S][i];}for(int i = 0; i < N; i++){//大循环minx = INT_MAX;for(int j = 0; j < N; j++){//寻找没有被标记并且最短的路径，并记录此结点 if(!book[j] && minx > dist[j]){minx = dist[j];u = j;} }book[u] = 1;for(int k = 0; k < N; k++){//如果A到B的距离大于A到C的距离加C到B的距离，那么更新数据if(!book[k] && dist[k] > dist[u]+v[u][k]){dist[k] = dist[u]+v[u][k];}}}
}

例题：

一、落谷P1339 [USACO09OCT]Heat Wave G
AC代码：

#include<stdio.h>
#include <cstring>
#include<limits.h>
#include<iostream>
using namespace std;int v[2505][2505];//存储邻接矩阵图 
int dist[2505];//dist[i]表示到i结点的最短路
int book[2505];//标记该结点是否访问 
int n, m, s, t;
void dijkstra(){//一个大循环套两个小循环 int u, min;book[s] = 1;for(int i = 1; i <= n; i++){//dist数组初始化，把起点到各点的权值赋值给dist dist[i] = v[s][i];}for(int k = 1; k <= n; k++){//大循环 min = INT_MAX;for(int i = 1; i <= n; i++){//寻找没有被标记并且最小的权值，并记录该结点 if(!book[i] && min > dist[i]){min = dist[i];u = i;}}book[u] = 1;for(int i = 1; i <= n; i++){//更新dist数组，如果A到B的距离大于A到C到B的距离，则更新A到B的最短距离 if(!book[i] && dist[i] > dist[u]+v[u][i]){dist[i] = dist[u]+v[u][i];}}} 
}
int main(){scanf("%d %d %d %d", &n, &m, &s, &t);//初始化v数组，最大数
//	for(int i = 0; i < 2500; i++){
//		fill(v[i], v[i]+2500, INT_MAX);
//	} memset(v, 0x3f, sizeof v);for(int i = 1; i <= m; i++){int u, g, w;scanf("%d %d %d", &u, &g, &w);v[u][g] = v[g][u] = min(v[u][g], w);}dijkstra(); printf("%d", dist[t]);
}

下面代码可输出最短路径所经过的结点（dijkstra + dfs）：

#include<cstdio>
#include<iostream>
#include<climits>
#include<cstring>
using namespace std;int N, M, S, D;
int dist[510];//dist[i]存储S到i结点的最短距离 
int book[510];//标记i结点是否访问 
int pre[510];//存储最短路径所经过的结点 
int v[510][510];//存储图信息 void dijkstra(){int u, minx;book[S] = 1;for(int i = 0; i < N; i++){dist[i] = v[S][i];}for(int i = 0; i < N; i++){minx = INT_MAX;for(int j = 0; j < N; j++){//寻找没有被标记并且最短的路径，并记录此结点 if(!book[j] && minx > dist[j]){minx = dist[j];u = j;} }book[u] = 1;for(int k = 0; k < N; k++){if(!book[k] && dist[k] > dist[u]+v[u][k]){dist[k] = dist[u]+v[u][k];pre[k] = u;} else if(!book[k] && dist[k] == dist[u]+v[u][k]){pre[k] = u;}}}
}
void dfs(int start, int end){if(start == end){printf("%d ", start);return;}dfs(start, pre[end]);printf("%d ", end);
}
int main(){scanf("%d %d %d %d", &N, &M, &S, &D);fill(v[0], v[0]+510*510, INT_MAX-1);for(int i = 0; i < M; i++){int a, b, c, d;scanf("%d %d %d", &a, &b, &c);v[a][b] = v[b][a] = min(v[a][b], c);}dijkstra();dfs(S, D);printf("%d", dist[D]);return 0;
}

二、1030 Travel Plan (30分)——C/C++（dijsktra + DFS）
AC代码：

#include<cstdio>
#include<iostream>
#include<climits>
#include<vector>
using namespace std;int N, M, S, D;
int dist[510];//dist[i]存储S到i结点的最短距离 
int book[510];//标记i结点是否访问 
int v[510][510];//存储图信息 
int cost[510][510];//存储花费信息 
vector <int> pre[510];//存储最短路径所经过的结点 
vector <int> path, temppath;
int mincost = INT_MAX;void dijkstra(){fill(dist, dist+510, INT_MAX-1);int u, minx;pre[S].push_back(S);dist[S] = 0;for(int i = 0; i < N; i++){minx = INT_MAX;for(int j = 0; j < N; j++){//寻找没有被标记并且最短的路径，并记录此结点 if(!book[j] && minx > dist[j]){minx = dist[j];u = j;} }book[u] = 1;for(int k = 0; k < N; k++){if(!book[k] && v[u][k] != INT_MAX){if(dist[k] > dist[u]+v[u][k]){dist[k] = dist[u]+v[u][k];pre[k].clear();pre[k].push_back(u);} else if(dist[k] == dist[u]+v[u][k]){pre[k].push_back(u);}}}}
}
void dfs(int v){temppath.push_back(v);if(S == v){int tempcost = 0;for(int i = temppath.size()-1; i >= 1; i--){int id = temppath[i], id1 = temppath[i-1];tempcost += cost[id][id1];}if(mincost > tempcost){mincost = tempcost;path = temppath;}temppath.pop_back();return;}for(int i = 0; i < pre[v].size(); i++){dfs(pre[v][i]);}temppath.pop_back();
}
int main(){scanf("%d %d %d %d", &N, &M, &S, &D);fill(v[0], v[0]+510*510, INT_MAX-1);for(int i = 0; i < M; i++){int a, b, c, d;scanf("%d %d %d %d", &a, &b, &c, &d);v[a][b] = v[b][a] = min(v[a][b], c);cost[a][b] = cost[b][a] = d;}dijkstra();dfs(D);for(int i = path.size()-1; i >= 0; i--){printf("%d ", path[i]);}printf("%d %d", dist[D], mincost);return 0;
}

三、题目连接：洛谷P3317

AC代码：

#include<cstdio>
#include<iostream>
#include<climits>
using namespace std;
struct Edge{int to, w, next;
}edge[1000010];int dist[10010];
int head[10010];
int book[10010];
int n, m, s, idx = 1;void add(int a, int b, int c){edge[idx].to = b;edge[idx].w = c;edge[idx].next = head[a];head[a] = idx++; 
}
void dijkstra(){fill(dist, dist + 10010, INT_MAX);dist[s] = 0;int temp = s;while(!book[temp]){book[temp] = 1;for(int i = head[temp]; i != -1; i = edge[i].next){if(!book[edge[i].to] && dist[edge[i].to] > dist[temp] + edge[i].w){dist[edge[i].to] = dist[temp] + edge[i].w;}}int minn = INT_MAX;for(int i = 1; i <= n; i++){if(!book[i] && minn > dist[i]){minn = dist[i];temp = i;}}}
}
int main(){fill(head, head + 10010, -1);scanf("%d %d %d", &n, &m, &s);for(int i = 0; i < m; i++){int a, b, c;scanf("%d %d %d", &a, &b, &c);add(a, b, c);}dijkstra();for(int i = 1; i <= n; i++){if(i < n)printf("%d ", dist[i]);elseprintf("%d", dist[i]);}return 0;
}