专栏首页工科狗和生物喵【图】Dijkstra算法

【图】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.

[进程已完成]

正文之后

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

本文分享自微信公众号 - 工科狗和生物喵(gh_3507b116a1f8),作者:HustWolf

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图算法|Dijkstra算法python实现

    01 — Dijkstra算法的理论部分 关于Dijkstra算法的原理部分,请参考之前的推送: 图算法|Dijkstra最短路径算法 Dijkstra算法总...

    double
  • 图论--Dijkstra算法总结

    1.BFS转换Dijkstra: 对于一些路径的的问题及一些特殊的搜索题目,如果数据量很多但是处理边的复杂程度可以接受,就是说我们可以通过操作将原来要搜索的问题...

    风骨散人Chiam
  • 图算法|Dijkstra最短路径算法

    01 — 单源最短路径 首先解释什么是单源最短路径,所谓单源最短路径就是指定一个出发顶点,计算从该源点出发到其他所有顶点的最短路径。如下图所示,如果源点设为A,...

    double
  • Dijkstra算法

    Dijkstra算法使用了广度优先搜索解决赋权有向图(或无向图)的单源最短路径问题。

    mwangblog
  • 图算法之bfs、dfs、prim、Dijkstra

    概述 在图算法中经常要执行遍历每个顶点和每条边的操作,即图搜索。许多图算法都以图搜索为基础,如2-着色问题、连通性计算基于深度优先搜寻(depth-first ...

    xiangzhihong
  • Dijkstra算法求图中最短路径

    在此借用上一篇文章[深度优先搜索(DFS)两点之间的可行路径](深度优先搜索(DFS)两点之间的可行路径)中的例子:

    带萝卜
  • 【(图) 旅游规划 (25 分)】【Dijkstra算法】

    _DIY
  • Dijkstra算法例子

    %d 输出 向量 路径长度,若t==[],则返回从起点到所有节点的路径长度

    mwangblog
  • dijkstra算法python实现

    py3study

扫码关注云+社区

领取腾讯云代金券