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

用vector<edge> es[MAX]表示点,每个点队列里放着点的相邻边和到边的距离。

以下源码经过测试可运行
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

#define MAX 10000 //MAX表示最大节点数
#define INF 10000 //设定两个节点之间不可达的情况下权重为INF

struct edge {
    int to,cost;      //每条边都有一个目的节点和权重
};


vector<edge> es[MAX]; //边的数组元素是以edge为元素的队列

int d[MAX];  //节点i到所有节点的距离
int v,e;  //节点个数和边的个数

//构造图
void build()
{
    printf("please input the number of vertex and edge\n");
    scanf("%d %d",&v,&e);
    printf("please input from,to,and cost of all edges\n");
    for(int i=0;i<e;i++)
    {
        int from,to,cost;
        edge epair1,epair2;
        scanf("%d %d %d",&from,&to,&cost);
        epair1.to=to;
        epair1.cost=cost;
        es[from].push_back(epair1);
        epair2.to=from;
        epair2.cost=cost;
        es[to].push_back(epair2);
    }
}
//求得节点s到所有节点的最短路径
void shortest_path(int s)
{
    for(int i=0;i<v;i++)
    {
        d[i]=INF;
    }
    d[s]=0;
    while(true)
    {
        bool update = false;
            for(int i=0;i<v;i++)
    {
        for(int j=0;j<es[i].size();j++)
        {
            if(d[i]!=INF&&es[i][j].cost+d[i]<d[es[i][j].to])
            {
                d[es[i][j].to]=d[i]+es[i][j].cost;
                update = true;
            }
        }
    }
    if(!update)
    {
        break;
    }
    }

}

int main()
{
    build();
    shortest_path(0);
    for(int i=0;i<v;i++)
    {
        printf("%d ",d[i]);
    }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python学习指南

python生成式

本篇将介绍Python的列表生成式,更多内容请参考:Python列表生成式 列表生成式即List Comprehensions,是Python内置的非常简...

24280
来自专栏kalifaの日々

POJ2431-最优队列(最小堆)解法

这道题有一个坑,就是给出的加油站到终点的距离不一定是降序排列好了的。 所以得到input之后要先对数据进行排序。我直接用了#include<algorithm>...

36370
来自专栏蜉蝣禅修之道

基于Huffman编码的压缩软件的Python实现

24640
来自专栏Golang语言社区

Go语言 -浮点数

Go提供了两种size的浮点数,float32和float64。它们的算术规范是由IEEE754国际标准定义,现代CPU都实现了这个规范。 浮点数能够表示的范...

41140
来自专栏WD学习记录

牛客网 和为S的两个数字

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

19240
来自专栏小樱的经验随笔

统计0到n之间1的个数[数学,动态规划dp](经典,详解)

问题描述 给定一个十进制整数N,求出从1到N的所有整数中出现”1”的个数。 例如:N=2时 1,2出现了1个 “1” 。 N=12时 1,2,3,4,5,6,...

36280
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之数值的整数次方(九度OJ1514)

题目描述: 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 输入: 输入可能包含多个测试样例。 ...

22570
来自专栏个人分享

调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相...

13830
来自专栏Python爬虫与数据挖掘

浅谈网络爬虫中广度优先算法和代码实现

前几天给大家分享了网络爬虫中深度优先算法的介绍及其代码实现过程,没来得及上车的小伙伴们可以戳这篇文章——浅谈网络爬虫中深度优先算法和简单代码实现。今天小编给大家...

9710
来自专栏编程

从机器学习学python(一)——numpy中的shape、tile、argsort

从机器学习学python(一) ——numpy中的shape、tile、argsort (原创内容,转载请注明来源,谢谢) 注:本系列是我在学习机器学习过程中,...

20450

扫码关注云+社区

领取腾讯云代金券