Dijkstra求单源最短路问题，常用于无负权图中：
该算法核心是每次贪心选取出未标记点中最小的边权，用该边权去松弛缩小其它的边权。之所以需要是最小的边权，是因为如果不是最小边权去松弛比它小的边只会让这个小边权变大，所以从最小开始，操作完进行标记继续找剩余中的最小边，直至操作完N次。
还需要注意图是有向的还是无向的，其中无向图需要map[i][j]==map[j][i]！
题目描述 长江游艇俱乐部在长江上设置了n 个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1<=i<=j<=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n 所需的最少租金。 对于给定的游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1<=i<j<=n，编程计算从游艇出租站1 到游艇出租站n所需的最少租金。 保证计算过程中任何时刻数值都不超过10^6 输入输出格式 输入格式： 由文件提供输入数据。文件的第1 行中有1 个正整数n（n<=200），表示有n个游艇出租站。接下来的n-1 行是一个半矩阵r(i,j),1<=i<j<=n。 输出格式： 程序运行结束时，将计算出的从游艇出租站1 到游艇出租站n所需的最少租金输出到文件中。 输入输出样例 输入样例#1： 3 5 15 7 输出样例#1：
12
简单的求最短通路问题：从1到n的最短通路（起点为1终点是n），并且此图是有向图。
#include<iostream> #include<cstring> #define inf 0x3f3f3f3f using namespace std; int n, pos; int map[300][300], dis[300], vis[300]; void dijkstra() { memset(dis, inf, sizeof(dis)); dis[1] = 0; vis[1] = 1; for (int i = 1; i <= n; i++) { dis[i] = map[1][i]; } for (int i = 1; i <=n; i++) //进行n次操作 { int minn = inf; for (int j = 1; j <=n; j++) //寻找剩余的最小值 { if (!vis[j]) { if (dis[j] < minn) { pos = j; minn = dis[j]; } } } vis[pos] = 1; for (int j = 1; j <=n; j++) //判断能否进行松弛操作 { if (dis[pos] + map[pos][j] < dis[j]) dis[j]=dis[pos] + map[pos][j]; } } } int main() { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (i == j) map[i][j] = 0; else map[i][j] = inf; } for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) { cin >> map[i][j]; //注意这是个有向图，租站之间是单向的：map[i][j]!=map[j][i] } dijkstra(); cout << dis[n] << endl; //dis[n]即为从1到n的最短路 return 0; } //进行n次操作 { int minn = inf; for (int j = 1; j <=n; j++) //寻找剩余的最小值 { if (!vis[j]) { if (dis[j] < minn) { pos = j; minn = dis[j]; } } } vis[pos] = 1; for (int j = 1; j <=n; j++) //判断能否进行松弛操作 { if (dis[pos] + map[pos][j] < dis[j]) dis[j]=dis[pos] + map[pos][j]; } } } int main() { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (i == j) map[i][j] = 0; else map[i][j] = inf; } for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) cin >> map[i][j]; //注意这是个有向图，租站之间是单向的：map[i][j]!=map[j][i] dijkstra(); cout << dis[n] << endl; //dis[n]即为从1到n的最短路 return 0; }
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.
For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.
此题与基本的dijkstra不同的是除了边权集还另需记录点权集并选取单源最短路的最大点集，同时记录起点到终点的通路有多少条。st为起点ed是终点。
那么同dis表示起点到各个点的距离一样，需要另设一个maxx来表示起点到各个点时的点权之和，目的是要得到最小的dis[ed]同时maxx[ed]尽可能最大，需要在基本dijkstra算法上进行变形。
#include<iostream> #include<cstring> #define inf 0x3f3f3f3f using namespace std; int map[510][510],man[510],box[510],vis[510]; //新增man记录每个点的点权，box记录路径条数 int dis[510],maxx[510]; int n,m,st,ed; void dijkstra(){ for(int i=0;i<n;i++) dis[i]=map[st][i]; //初始化dis，maxx不确定先全为零 dis[st]=0;maxx[st]=man[st];box[st]=1; //起点初始化 while(1){ int minn=inf,pos; for(int i=0;i<n;i++){ //寻找最小值 if(vis[i]) continue; if(dis[i]<minn) { minn=dis[i]; pos=i; } } if(minn==inf||pos==ed) //如果minn==inf说明没有最小值了，或者已经松弛到了ed就不需要再考虑其它点了 break; vis[pos]=1; for(int i=0;i<n;i++){ if(vis[i]||map[pos][i]==inf) //如果该点选中过或者map[pos][i]此路不通，则跳过 continue; if(dis[pos]+map[pos][i]<dis[i]){ maxx[i]=maxx[pos]+man[i]; //对边进行松弛同时相应操作maxx和box dis[i]=dis[pos]+map[pos][i]; box[i]=box[pos]; } else if(dis[pos]+map[pos][i]==dis[i]){ box[i]+=box[pos]; //到该点的通路增加，同时确定是否更新到该点的最大点权和 if(maxx[i]<maxx[pos]+man[i]) maxx[i]=maxx[pos]+man[i]; } } } } int main(){ cin>>n>>m>>st>>ed; for(int i=0;i<n;i++) cin>>man[i]; memset(map,inf,sizeof(map)); for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; map[a][b]=map[b][a]=c; //注意此题明显是一个无向图！从城市a到城市b和从b到a的道路长度是相同的！ } dijkstra(); cout<<box[ed]<<' '<<maxx[ed]<<endl; return 0; }
