【PAT】advanced_1003. Emergency(最短路径算法)
@(PAT)
首先利用这道题要复习一下最短路径算法，经典的最短路径算法有两个：Floyd算法和Dijkstra算法。
Floyd算法
关于Floyd算法，基本思路如下：
1. 使用d来存储图，d[i][j]表示从i到j路径的长度，设为无穷大表示路径不存在。使用path存储路径，path[i][j]表示从i到j的最后经过的节点。
2. 在节点A和B之间，寻找是否存在一个中间节点C，使得A到C，C到B的路径比直接A到B的路径短，如果存在，就更新d和path。
3. 使用3层循环，最外层的是中间点的循环，内两层循环为节点A和B的循环，意思是每个节点当作中间节点，然后看每两个时间是否存在更短的路径。
4. 因为遍历了每种情况，所以能够解决节点A和B之间存在2个中间节点使路径更短的情况，因为随着循环的进行，每次解决存在一个中间节点的情况，最终A和B存在N个中间节点的情况都会成为A和B存在一个中间节点C使得路径最短的情况。
另外关于floyd算法，一个需要注意的地方就是它是全局的，会把d的所有数据都更新为最短的路径。
核心代码如下（3层循环）：
for (int k= 0; k< n; k++) {
for (int i= 0; i< n; i++) {
for (int j= 0; j< n; j++) {
if (i== j) continue;
if (d[i][k]+ d[k][j]< d[i][j]) {
d[i][j]= d[i][k]+ d[k][j];
path[i][j]= path[i][k];
}
}
}
}Dijkstra算法
该算法非常经典，以前没有好好研究，在计算机网络中也有用到，比较重要，现在趁这道题好好研究该算法。
参考blog，结合过程图理解过程:
http://www.cnblogs.com/skywang12345/p/3711512.html
https://www.61mon.com/index.php/archives/194/
与floyd算法不同，dijkstra算法只能找到给定初始点到图上其他的每个点的距离。
理解了过程后，从代码出发，该算法主要有以下方面：
1. 用二维数组mat存储图，如果i和j之间不存在边，则mat[i][j]设置为无穷大。
2. 算法需要借助3个数组：存储路径的prev、存储最短路径长度的dist和当前是否已经找到初始点与该点的最短距离flag。需要将它们初始化，prev和flag初始化为0，dist初始化为mat中初始点C1到其他点的初始距离。
3. 对初始点数据进行初始化，flag为1，dist为0。
4. 进行n- 1循环（n为点数），每次循环都找到初始点C1到另外一个点的最短路径。
5. 每次n-1循环中，遍历n次，在没找过的点（flag== 0）中，寻找dist最短的点K。找到之后，将之记录为已经找过（flag== 1，加入在已经寻找过的集合中）。然后再遍历n次，对与之不相连的点（mat[k][j]>= MY_MAX）不作处理，对与之相连的点P，如果寻找到的最短dist（初始点C1到K的距离）加上边K到P的边的长度比初始点到P的距离(dist[j])短，则将C1到P更新为最短dist（初始点C1到K的距离）加上边K到P的边的长度，并更新prev数组记录路径。
6. 最后得到的flag应该全部为1，dist存储的是初始点C1到各点的最短路径，prev存储的是C1到目标点M的最短路径的M之前的一点。
结合本题的数据和输入，初步使用dijkstra算法的code如下：
#include <iostream>
#include <vector>
using namespace std;
#define MY_MAX 99999
int main() {
int n, m, c1, c2;
scanf("%d %d %d %d", &n, &m, &c1, &c2);
vector<int> num_RT;
for (int i= 0; i< n; i++) {
int temp;
scanf("%d", &temp);
num_RT.push_back(temp);
}
// adjacency matrix
int mat[500][500];
for (int i= 0; i< n; i++) {
for (int j= 0; j< n; j++) {
mat[i][j]= MY_MAX;
}
}
for (int i= 0; i< m; i++) {
int x, y, d;
scanf("%d %d %d", &x, &y, &d);
mat[x][y]= d;
mat[y][x]= d;
}
int prev[500];
int dist[500];
int flag[500];
// initialize
for (int i= 0; i< n; i++) {
flag[i]= 0;
prev[i]= 0;
dist[i]= mat[c1][i];
}
flag[c1]= 1;
dist[c1]= 0;
int min;
int k= 0;
// loop for n-1 times
for (int i= 1; i< n; i++) {
min= MY_MAX;
for (int j= 0; j< n; j++) {
if (flag[j]== 0&& dist[j]< min) {
min= dist[j];
k= j;
}
}
flag[k]= 1;
int temp;
for (int j= 0; j< n; j++) {
if (mat[k][j]>= MY_MAX) {
temp= MY_MAX;
} else {
temp= min+ mat[k][j];
}
if (flag[j]== 0&& temp< dist[j]) {
dist[j]= temp;
prev[j]= k;
}
}
}
for (int i= 0; i< n; i++) {
cout<< dist[i]<< endl;
}
}现在回到题目上来。题目要求输出的是c1和c2之间的最短路径的数目和最短路径的最大权重和。基于基本的dijkstra算法，思路如下：
1. 在第一层循环中，找到最小边后，再进行一次遍历的时候，需要更改原来基本的dijkstra算法。
2. 如果找到了新的最短路径，则更新最短路径，同时该点的最短路径数目和前驱的最短路径数目是相同的（因为新加的边已经是最短的路径）同时增加新增点的权值。
3. 如果找到了相等的最短路径，则到该点的最短路径数目为原来找到的数目和新找到的数目和，同时取较大的权值和。
我的AC代码如下：
#include <iostream>
#include <vector>
using namespace std;
#define INF 99999
int main() {
int n, m, start, end;
scanf("%d%d%d%d", &n, &m, &start, &end);
vector<int> weight;
for (int i= 0; i< n; i++) {
int temp;
scanf("%d", &temp);
weight.push_back(temp);
}
// initialize adjacent matrix
vector< vector<int> > mat;
vector<int> tempv;
for (int i= 0; i< n; i++) {
tempv.push_back(INF);
}
for (int i= 0; i< n; i++) {
mat.push_back(tempv);
}
// save the edge of the graph
for (int i= 0; i< m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
mat[a][b]= c;
mat[b][a]= c;
}
// use count to save the num of shortest paths
vector<int> count;
// use maxAmt to save the max amount of teams
vector<int> maxAmt;
// use visited to save if the point if visited by Dijkstra Algorithm
vector<bool> visited;
// use d to save the shortest distance
vector<int> d;
// initialize
for (int i= 0; i< n; i++) {
count.push_back(0);
maxAmt.push_back(weight[i]);
visited.push_back(false);
d.push_back(mat[start][i]);
}
// the adjacent points of start
for (int i= 0; i< n; i++) {
if (d[i]< INF) {
count[i]= 1;
maxAmt[i]+= weight[start];
}
}
// the start point
visited[start]= true;
d[start]= 0;
count[start]= 1;
// begin Dijkstra loop
for (int i= 1; i< n; i++) {
int min_d= INF;
int min_i= 0;
for (int j= 0; j< n; j++) {
if (!visited[j]&& d[j]< min_d) {
min_d= d[j];
min_i= j;
}
}
visited[min_i]= true;
for (int j= 0; j< n; j++) {
if (!visited[j]) {
if (min_d+ mat[min_i][j]< d[j]) {
d[j]= min_d+ mat[min_i][j];
count[j]= count[min_i];
maxAmt[j]= maxAmt[min_i]+ weight[j];
} else if (min_d+ mat[min_i][j]== d[j]) {
count[j]+= count[min_i];
maxAmt[j]= max(maxAmt[j], maxAmt[min_i]+ weight[j]);
}
}
}
}
printf("%d %d", count[end], maxAmt[end]);
}注意dijkstra算法中，循环内的第一次循环是找到最小路径的点的，找到该点后就以该点为依据，找和这个点相邻的点，然后根据是比d更小还是相等而采取相应的操作。
该代码研究了好一会儿才写出来的，不太优雅，希望慢慢消化以后更新一个更加优雅的版本。另外，最短路径算法是经常被用来考察的点，务必要好好消化！