最短路径——迪杰斯特拉（Dijkstra)算法

前言：

马上新一轮的ACM考核就要来了，而这一次的考核内容包括了弗洛伊德算法，而由于弗洛伊德算法是由迪杰斯特拉算法改进而得到的，所以准备先复习这个算法，然后随便找道题写一下。

旅游规划

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:

输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出格式:

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
结尾无空行

输出样例:

3 40
结尾无空行

原理：

• 首先，选定一个点v 0 v0v0，先假设所有的点到某个点的路径都是无穷（当然自己到自己肯定得是长度是0…）。
• 然后确定一个集合S SS，这集合表示已经被访问的过点。（那么没有被访问过的点，也是很容易解决的…），这里用个bool数组什么的标记一下吧。
• 之后，先更新所有点到这个v 0 v0v0的距离。怎么更新呢？
• 所有点通过已经被访问过的点到达v 0 v0v0的距离，在结合d ( v 0 , v i ) = m i n v j ∈ ( S ) ( d ( v 0 , v j ) + w ( v j , v i ) ) d(v0, vi) = min_{vj \in (S)}(d(v0, vj) + w(vj, vi))d(v0,vi)=min vj∈(S)(d(v0,vj)+w(vj,vi)) ( 一般就是新增加的那个点考虑下就好了 )。就是在中间搭一个桥，如果，通过这个桥的点会让这个路变得更近，就更新这个路径的长度。
• 然后选个最近的点，然后把这个最近的点标记访问过。纳入到集合S SS
• 然后，一直到把所有的点都纳入进去之后，就没什么事情了~

是不是感觉直接看不懂？小问题，我将通过借助此题来解释其原理。
首先我们画出这个旅游图：

这里我们需要注意这是高速公路，是双向的。
这个算法的目的是算出一个节点到其他所有节点的最短路径，所以我们首先就需要一个大小为节点数的一维数组来存储最短路径的值。如Path[4]={0,1,2,4}，这里我们先存储能直接到达的，不能到达就用正无穷表示，而出发地自然用0表示。然后我们还需要一个bool数组来存储是否算出了最短路径。初始化后的arrived[4]={true,false,false,false}，然后我们找出没达到过的里面的最短的路径，明显是节点1，并将其置为已到达过即为arrived[4]={true,true,false,false}，然后遍历节点1所能到达的所有节点，并把权重相加后与原始Path里的最短路径相比较，然后比它小，就更新它，第一次比较后：**Path[4]={0,1,2,3}**，直到所有节点都访问过，这样我们就得到了所有的最短路径。

源码：

#include<iostream>
#include<cstring>
const int N=500;
const int INf=999999;//代表正无穷
int map[N][N][2];//同时存储路径长度和费用
using namespace std;
int answer[2];//结果
int n;
void minpath(int s,int e){
    int dis[n][2],t=INf,flag;
    bool arrived[n];
    memset(arrived,false,sizeof(arrived));
    memset(dis,INf,sizeof(dis));
    arrived[s]=true;
    //初始化最短路径
    for(int i=0;i<n;i++){
        dis[i][0]=map[s][i][0];
        dis[i][1]=map[s][i][1];
    }
    dis[s][0]=0;dis[s][1]=0;
    for(int i=0;i<n;i++){
        flag=0;t=INf;
        for(int j=0;j<n;j++){
            if(!arrived[j]&&dis[j][0]<t){
                t=dis[j][0];
                flag=j;
            }
        }
        arrived[flag]=true;
        for(int j=0;j<n;j++){
            if(!arrived[j]&&dis[flag][0]+map[flag][j][0]<dis[j][0]){
                dis[j][0]=dis[flag][0]+map[flag][j][0];
                dis[j][1]=dis[flag][1]+map[flag][j][1];
            }else if(!arrived[j]&&dis[flag][0]+map[flag][j][0]==dis[j][0]&&dis[flag][1]+map[flag][j][1]<dis[j][1]){//取费用最小的
                dis[j][1]=dis[flag][1]+map[flag][j][1];
            }
        }
    }
    //得出结果
    answer[0]=dis[e][0];
    answer[1]=dis[e][1];
}
int main(){
    int m,start,end,s,d,v,p;
    cin>>n>>m>>start>>end;
    //初始化地图
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j){
                map[i][j][0]=0;
                map[i][j][1]=0;
            }else{
                map[i][j][0]=INf;
                map[i][j][1]=INf;
            }
        }
    }
    //录入地图
    for(int i=0;i<m;i++){
        cin>>s>>d>>v>>p;
        map[s][d][0]=v;
        map[s][d][1]=p;
        map[d][s][0]=v;
        map[d][s][1]=p;
    }
    minpath(start,end);
    cout<<answer[0]<<" "<<answer[1];
    return 0;
}