文档章节

C++的迪杰斯特拉

侯禹
 侯禹
发布于 2013/09/23 22:52
字数 269
阅读 114
收藏 3
点赞 0
评论 0
/*    Dijkstra(不存在负环回路的情况下)     */
#include <iostream>
#include <cstdio>
#include <cstring>
#define Inf 0x7fffffff
#define MaxV 10000
using namespace std;
int N,M;
int map[MaxV][MaxV];
int dist[MaxV];     //记录当前节点最短路径
int path[MaxV];     //记录最短路径前一节点
bool p[MaxV];
void dijkstra(int s)
{
    int i,j,k;
    int min;
    for(i=0;i<=N;i++)             //初始化非源点信息
    {
        p[i]=false,dist[i]=map[s][i],path[i]=s;
    }
    dist[s]=0,path[s]=s,p[s]=true;   //源点信息
    for(i=1;i<=N;i++)
    { 
        min=Inf;
        k=0;
        for(j=1;j<=N;j++)
        {
            if(!p[j]&&dist[j]<min)
            {
                min=dist[j];
                k=j;
            }
        }
        if(k == 0) {printf("buzhogn \n"); return;}
        p[k]=true;
        for(j=1;j<=N;j++)
        {
            if(!p[j]&&map[k][j]!=Inf&&dist[j]>dist[k]+map[k][j])
            {
                dist[j]=dist[k]+map[k][j];
                path[j]=k;
            }
        }
    }
}
void init()
{
    int from,to,w;
    scanf("%d%d",&N,&M);
    for(int i=0;i<=N;i++)
    for(int j=0;j<=N;j++)
    {
        if(i==j)    map[i][j]=0;
        else        map[i][j]=Inf;
    }
    for(int i=0;i<M;i++)
    {
        scanf("%d%d%d",&from,&to,&w);
        map[from][to]=map[to][from]=w;
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    init();
    dijkstra(1);
    for(int i=1;i<=N;i++)
    printf("dist[%d]   =   %d\n",i,dist[i]);
    return 0;
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 94
博文 49
码字总数 34362
作品 0
海淀
程序员
Java程序员如何高效而优雅地入门C++

Java程序员如何高效而优雅地入门Cpp,由于工作需要,需要用C++写一些模块。关于C++ 的知识结构,虽说我有过快速学习很多新语言的经验,但对于C++ 我也算是老手,但也还需要心生敬畏,本文会从...

小欣妹妹 ⋅ 04/23 ⋅ 0

传微软已同意收购GitHub,最早周一宣布交易

传微软已同意收购GitHub,最早周一宣布交易 2018-06-04 13:37编辑: suiling分类:业界动态来源:网易科技 微软Github微软收购GitHub 招聘信息: C++工程师 Cocos2d-x游戏客户端开发 iOS开发...

suiling ⋅ 06/04 ⋅ 0

C语言/C++编程新手学习常见问题

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/11 ⋅ 0

单片机C语言编程学习简介与第一个C语言程序

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/26 ⋅ 0

C语言/C++程序员编程学习自信心曲线图

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/10 ⋅ 0

VS2010/MFC编程入门教程之目录和总结(鸡啄米)

鸡啄米的这套VS2010/MFC编程入门教程到此就全部完成了,虽然有些内容还未涉及到,但帮助大家进行VS2010/MFC的入门学习业已足够。以此教程的知识为基础,学习VS2010/MFC较为深入的内容已非难事...

weixin_40647819 ⋅ 05/23 ⋅ 0

C语言/C++永远都不会过时的编程语言

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 03/30 ⋅ 0

C语言/C++编程学习强势之处的体现

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/12 ⋅ 0

《C++ primer》读后感:时代的经典

说起Lippman的C++ Primer,我总是有种特殊感情。这本书既是我进入C++领域的敲门砖,也是我第一次在网络上发表技术文章的对象。当年读书笔记中的青涩迷惘和年少轻狂都还历历在目,转眼已经从第...

凌杰_owlman ⋅ 05/15 ⋅ 0

C语言/C++编程学习未来之路

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 03/30 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

一篇文章学懂Shell脚本

Shell脚本,就是利用Shell的命令解释的功能,对一个纯文本的文件进行解析,然后执行这些功能,也可以说Shell脚本就是一系列命令的集合。 Shell可以直接使用在win/Unix/Linux上面,并且可以调用...

Jake_xun ⋅ 27分钟前 ⋅ 0

大数据工程师需要精通算法吗,要达到一个什么程度呢?

机器学习是人工智能的一个重要分支,而机器学习下最重要的就是算法,本文讲述归纳了入门级的几个机器学习算法,加大数据学习群:716581014一起加入AI技术大本营。 1、监督学习算法 这个算法由...

董黎明 ⋅ 59分钟前 ⋅ 0

Kylin 对维度表的的要求

1.要具有数据一致性,主键值必须是唯一的;Kylin 会进行检查,如果有两行的主键值相同则会报错。 2.维度表越小越好,因为 Kylin 会将维度表加载到内存中供查询;过大的表不适合作为维度表,默...

无精疯 ⋅ 今天 ⋅ 0

58到家数据库30条军规解读

军规适用场景:并发量大、数据量大的互联网业务 军规:介绍内容 解读:讲解原因,解读比军规更重要 一、基础规范 (1)必须使用InnoDB存储引擎 解读:支持事务、行级锁、并发性能更好、CPU及...

kim_o ⋅ 今天 ⋅ 0

代码注释中顺序更改 文件读写换行

`package ssh; import com.xxx.common.log.LogFactory; import com.xxx.common.log.LoggerUtil; import org.apache.commons.lang3.StringUtils; import java.io.*; public class DirErgodic ......

林伟琨 ⋅ 今天 ⋅ 0

linux实用操作命令

参考 http://blog.csdn.net/qwe6112071/article/details/50806734 ls [选项] [目录名 | 列出相关目录下的所有目录和文件 -a 列出包括.a开头的隐藏文件的所有文件-A 同-a,但不列出"."和"...

简心 ⋅ 今天 ⋅ 0

preg_match处理中文符号 url编码方法

之前想过直接用符号来替换,但失败了,或者用其他方式,但有有些复杂,这个是一个新的思路,亲测可用 <?php$str='637朗逸·超速新风王(300)(白光)'; $str=iconv("UTF-8","GBK",$s...

大灰狼wow ⋅ 今天 ⋅ 0

DevOps 资讯 | PostgreSQL 的时代到来了吗 ?

PostgreSQL是对象-关系型数据库,BSD 许可证。拼读为"post-gress-Q-L"。 作者: Tony Baer 原文: Has the time finally come for PostgreSQL?(有删节) 近30年来 PostgreSQL 无疑是您从未听...

RiboseYim ⋅ 今天 ⋅ 0

github太慢

1:用浏览器访问 IPAddress.com or http://tool.chinaz.com 使用 IP Lookup 工具获得github.com和github.global.ssl.fastly.net域名的ip地址 2:/etc/hosts文件中添加如下格式(IP最好自己查一...

whoisliang ⋅ 今天 ⋅ 0

非阻塞同步之 CAS

为解决线程安全问题,互斥同步相当于以时间换空间。多线程情况下,只有一个线程可以访问同步代码。这种同步也叫阻塞同步(Blocking Synchronization). 这种同步属于一种悲观并发策略。认为只...

长安一梦 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部