目录

适用情形

适用于权值为非负的图的单源最短路径

思想

在已知起点与终点的情况下。须有三个一维数组S，U，dis，S用于记录已经查找过的点，U则记录未查找到的点，dis用于记录从起点到各个点间的距离。开始时，S中仅有起点，U中则是其它所有点，dis[起点]初始化为0，dis中其它元素则为起点到各点的距离，如果没有路径则可以记录为INF(无穷大）或者-1。然后寻找与起点最近的点，将它加入数组S中，再更新dis的最短路径。然后再找与起点最近的点，将它加入数组S中，再更新dis的最短路径。知道全部更新完成。

核心代码

//假设已知起点为u，点间的距离已存到二维数组map中,点间没有路径则存INFint INF = 1e7;int map[100][100];int dis[100];int u = 0;int N = 100; //N表示城市的数量int flag[100]; //以数组flag记录点是否在数组S中void Dijkstra(){//第一步：初始化两个数组for(int i = 0; i < N; i++){dis[i] = map[u][i];flag[i] = 0;}flag[u] = 1;dis[u] = 0;//以循环来表示重复接下来的步骤，确保找到每个点for(int i = 0; i < N; i++){//第二步：找到距离起点的最近点int temp = INF, t = u;for(int j = 0; j < N; j++){if(!flag[j] && dis[j] < INF){t = j;temp = dis[j];}}if(t == u)return;//全部点已被找完则退出elseflag[t] = 1; //将找到的点加入S//第三步：更新dis数组for(int j = 0; j < N; j++){if(flag[j] == 0 && map[t][j]<INF && dis[j]>(dis[t]+map[t][j])){dis[j]=dis[t]+map[t][j];}}}}

我将DIjkstra算法分为了三个步骤，即：

第一步：初始化两个数组

第二步：找到距离起点的最近点

第三步：更新dis数组

其中第二和第三步需用循环满足所有的点都被搜一遍。

设计实现更多功能

1.记录路径

加入一个记录中转点的数组即可

2.计算最短路径的条数

加入一个记录到每个点的路径的数量的数组即可

3.出现路径长度相同的情况，根据每个点的权选择特定路径

加入一个记录到该点的权量的数组即可

…

总的来说，需要实现什么功能就加上一个记录数据变化的数组即可。具体会在下面举例说明

举例说明

题目

分析：在这道题目中我们发现，不仅需要寻找最短路径的长度，还需要找到最短路径的条数，已经救援队数量最多的那条最短路径，故我们需加入上一部分说的三个数组。具体代码如下：

#include<iostream>#define K 501using namespace std;int INF = 1e7;int N, M , S , D;int teamnumber[K]; //记录每个城市的救援队数量int map[K][K]; //记录城市间的路径距离int father[K]; //记录中转点int dis[K];//记录起点到个点间的距离int flag[K]; //记录每个点是否已经搜索int number[K]; //记录起点到各点时路径的数量int ts[K]; //记录救援队的数量void Dijkstra(){//各数组的初始化fill(dis, dis+N, INF);fill(flag,flag+N, 0);fill(number, number+N, 0);fill(ts, ts+N, 0);for(int i = 0; i < N; i++){dis[i] = map[S][i];father[i] = i;}//我们保持flag[i] == 0,在第一次搜索中会首先检索到它,你也可以思考一下让它为0有什么好处dis[S] = 0;number[S] = 1;ts[S] = teamnumber[S];//开始搜索每个点for(int i = 0; i < N; i++){int Min = INF, t = -1;for(int j = 0; j < N; j++){if(flag[j] == 0 && dis[j] < Min){Min = dis[j];t = j;}}if(t == -1)return;elseflag[t] = 1;for(int j = 0; j < N; j++) //注意两条路距离相同但权值不同的情况，故分两种情况讨论{if(flag[j] == 0 && (dis[t] + map[t][j]) < dis[j] && map[t][j] < INF){dis[j] = dis[t] + map[t][j];father[j] = t;ts[j] = ts[t] + teamnumber[j];number[j] = number[t];}else if(flag[j] == 0 && (dis[t] + map[t][j]) == dis[j] && map[t][j] < INF){if((ts[t] + teamnumber [j]) > ts[j]){ts[j] = ts[t] + teamnumber[j];father[j] = t;}number[j] += number[t];}}}}//打印路径函数void PP(int s, int d){while(father[d] != d){PP(s,father[d]);cout << father[d] << " ";return;}return;}int main(){cin >> N >> M >> S >> D;for(int i = 0; i < N; i++)cin >> teamnumber[i];for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){map[i][j] = INF;}}int n, m ,d;for(int i = 0; i < M; i++){cin >> n >> m >> d;map[n][m] = d;map[m][n] = d;}Dijkstra();cout << number[D] << " " << ts[D] << endl;PP(S,D);cout << D;return 0;}

需要注意的地方在代码上都有注释，如有问题可以在评论区提问。