【图】Dijkstra算法

正文之前

好久没弄C++了，上学期颓废了半学期，这学期开学就搞课程设计快疯了。待会要考试CSP，所以弄点代码储备，待会到了考场说不定能省点功夫！

正文

#include<iostream>
using namespace std;

#define  The_Bigest_Num  1000000
#define BIGEST  10000
int Tu[BIGEST][BIGEST];
bool Judge_IF_IS_IN_MIN[BIGEST];
int Distance[BIGEST];
int Qian_Qu[BIGEST];

void dijkstra(int v0,int n)
{
    //初始化参数，设定所有与初始点相连的点的前驱点为初始点
    for(int i=1;i<=n;++i)
    {
        Judge_IF_IS_IN_MIN[i]=false;
        Distance[i]=Tu[v0][i];
        if(Distance[i]!=The_Bigest_Num)
            Qian_Qu[i]=v0;
        else
            Qian_Qu[i]=-1;
    }
    //设置初始点到初始点的距离为0，其他为Tu[v0][i];
    Distance[v0]=0;
    Judge_IF_IS_IN_MIN[v0]=true;
    //对除了初始点外的每个点进行最短路径的计算。
    for(int i=2;i<=n;++i)
    {
        int min_distance=The_Bigest_Num;
        int u=v0;
        for(int j=1;j<=n;++j)
        {
            //扫描每个点，如果不是处于最短路径状态并且距离小于当前最小距离，那么更新当前最小距离，并且找到出发点到某一点的最小距离。
            if(!Judge_IF_IS_IN_MIN[j] && Distance[j]<min_distance)
            {
                u=j;
                min_distance=Distance[j];
            }
        }
        //找到了初始点点到某一点的最小距离之后，从别的点开始找到当前点有么有更近的点。
        Judge_IF_IS_IN_MIN[u]=true;
        // int minQianQu=The_Bigest_Num;
        for(int j=1;j<=n;++j)
        {
            if(!Judge_IF_IS_IN_MIN[j] && Tu[u][j]<The_Bigest_Num) //Tu[u][j]<minQianQu)
            {
                if(Distance[j]>=Distance[u]+Tu[u][j])
                {
                    Distance[j]=Distance[u]+Tu[u][j];
                    Qian_Qu[j]=u;
                    // minQianQu=Tu[u][j];
                }
            }
        }
    }
    int all=0;
    for(int i=2;i<=n;++i)
    {
        if(Qian_Qu[i]!=1)
        {
            all+=(Distance[i]-Distance[Qian_Qu[i]]);
        }
        else
            all+=Tu[1][i];
    }
    cout<<all<<endl;
}


int main()
{
    int lines,size;
    cin>>size>>lines;
    for(auto &x:Tu)
        for(auto &s:x)
            s=The_Bigest_Num;
    while(lines--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        Tu[a][b]=c;
        Tu[b][a]=c;
    }
    dijkstra(1,size);
}

/*
样例输入
4 5
1 2 4
1 3 5
2 3 2
2 4 3
3 4 2

样例输出
11
*/

Output：

Last login: Sun Mar 18 12:09:36 on ttys000


= * = * = * = * = * = * = * = * = * = * = * = * = * = * 
✧｡٩(ˊᗜˋ)و✧* Hello！ Welcome 张照博！！开启愉快的一天吧！
= * = * = * = * = * = * = * = * = * = * = * = * = * = * 


HustWolf:~ zhangzhaobo$ /Users/zhangzhaobo/program/C++/Dijkstra ; exit;
4 5
1 2 4
1 3 5
2 3 2
2 4 3
3 4 2
11
logout
Saving session...
...copying shared history...
...saving history...truncating history files...
...completed.

[进程已完成]

正文之后

祝我好运！发誓这次考试后一定苦学！上学期太飘了。