专栏首页kalifaの日々C++迪杰斯特拉最短路径算法实现

C++迪杰斯特拉最短路径算法实现

input

第一行表示这个图有4条边,下面五行代表这个图的5条边。

4
0 2 2
0 1 5
1 3 2
2 3 6
-1 0 0

输入样例

out

分别输出结点“0”到结点0,1,2,3的最短距离。

0 5 2 7
源码
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
#define MAX 10000
#define INF 10000

class edge{
public:

    int to,cost;
    edge(int to,int cost)
    {
        this->to=to;
        this->cost=cost;
    }

};

vector<edge> G[MAX];
int d[MAX];
int v;

typedef pair<int,int> P;

void build()
{
    printf("input v\n");
    scanf("%d",&v);
    while(true)
    {
        int from,to,cost;
        scanf("%d %d %d",&from,&to,&cost);
        if(from<0)
        {
            break;
        }
        G[from].push_back(edge(to,cost));
        G[to].push_back(edge(from,cost));

    }
}

void dijkstra(int s)
{
    priority_queue< P,vector<P>,greater<P> > que;
    fill(d,d+v,INF);
    d[s]=0;
    que.push(P(0,s));

    while(!que.empty())
    {
        P p=que.top();
        que.pop();
        int v = p.second;
        if(d[v]<p.first) continue;
        for(int i=0;i<G[v].size();i++)
        {
            edge e = G[v][i];
            if(d[e.to]>d[v]+e.cost)
            {
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

vector<int> get_path(int des)
{
    vector<int> res;
    res.push_back(des);
    //printf("lalalala\n");
    while(des!=0)
    {

        vector<edge> edges = G[des];
        //printf("size of edges: %d\n",edges.size());
        for(int i=0;i<edges.size();i++)
        {
            //printf("%d %d\n",edges[i].to,edges[i].cost);
            if(d[des]==d[edges[i].to]+edges[i].cost)
            {
                //printf("前驱结点是:%d",i);
                res.push_back(edges[i].to);
                des = edges[i].to;
                break;
            }
        }
    }
    return res;
}

int main()
{
    build();
    dijkstra(0);
    for(int i=0;i<v;i++)
    {
        printf("%d ",d[i]);
    }
    vector<int> res = get_path(3);
    printf("从终点3到起点1的最短路径是:\n");
    for(int i=0;i<res.size();i++)
    {
        printf("%d ",res[i]);
    }

}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++构造无向图&求最短路径源码

    用vector<edge> es[MAX]表示点,每个点队列里放着点的相邻边和到边的距离。 以下源码经过测试可运行 #include <iostream> #i...

    kalifa_lau
  • C++二分图代码实现

    #include <iostream> #include <cstdio> #include <vector> using namespace std; #d...

    kalifa_lau
  • 素数相关问题练习 C++

    辗转相除 #include <iostream> using namespace std; int gcb(int a,int b) { if(b==...

    kalifa_lau
  • PHOTON——用于快速机器学习模型开发的Python API(CS-LG)

    本文介绍PHOTON的实现和使用,PHOTON是一个高级的Python API,旨在简化和加速机器学习模型的开发过程。它可以设计基本的和高级的机器学习流水线结构...

    Elva
  • [LintCode] Number of Islands(岛屿个数)

    0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

    HoneyMoose
  • python 16进制串(\xfe)转int

    超级大猪
  • Sim-to-Real: 仿真训练直接迁移到真实机器人

    用户1908973
  • 怎样学Python 第二十三课 模块化处理用户输入基础

    大家好,今天让我们来了解一个非常有用的模块,我很久以前就没有意识到这一点,这个模块允许我们简单而有效地使用命令行参数,它不仅会为我们处理这些争论,而且如果事情不...

    用户1631416
  • Conent7安装Docker-Compose

    由于国内原因,可能会出现类似github-production-release-asset-2e65be.s3.amazonaws.com连接失败的问题。

    汐楓
  • 币聪-曾经辉煌的NEO现在还好吗?权利下放,3.0版本能否再次逆袭

    区块链平台NEO,许多人认为将与比特币和以太坊一起作为加密货币的三位一体获得席位,已经发布了2018年7月的全球发展报告。在这里,我们回顾一下“中国的以太坊”的...

    币聪财经

扫码关注云+社区

领取腾讯云代金券