欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【图】Dijkstra算法

程序员文章站 2022-05-21 08:51:45
...

正文之前

好久没弄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.

[进程已完成]

正文之后

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