文档章节

C++的迪杰斯特拉

侯禹
 侯禹
发布于 2013/09/23 22:52
字数 269
阅读 118
收藏 3
/*    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;
}


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 95
博文 49
码字总数 34362
作品 0
海淀
程序员
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
0
0
4-C++远征之起航篇-学习笔记

c++教程起航篇 我们会讲C++那些事,C++与C语言的关系。 C++诞生于贝尔实验室。 C++之父: 本贾尼·斯特劳斯特卢普 C++社区排行榜 最新排行,c++排名第三,Python排名第四 C++语言的应用领域:...

天涯明月笙
07/20
0
0
C++之父评论C++与Java

如 果人们非要拿C++和Java来作比较,我建议他们去阅读The Design and Evolution of C++,看看C++为什么是今天这个样子,用我在设计C++时遵从的原则来检验这两种语言。这些原则与SUN的Java开发...

zplswf
2012/04/09
0
0
『七月直播』人工智能专场——用Python和C++,如何跻身科技前沿?

第一场——主题:人工智能学习与发展路线规划 7月19日(周四) 20:00 >主讲老师:唐宇迪 同济大学计算机博士,专注于机器学习与计算机视觉领域,深度学习领域一线实战专家,善于实现包括人脸...

51CTO学院
07/17
0
0
Java程序员如何高效而优雅地入门C++

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

小欣妹妹
04/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

八种排序算法的时间复杂度复杂度

1、稳定性 归并排序、冒泡排序、插入排序。基数排序是稳定的 选择排序、快速排序、希尔排序、堆排序是不稳定的 2、时间复杂度 最基础的四个算法:冒泡、选择、插入、快排中,快排的时间复杂度...

陈刚生
26分钟前
1
0
大数据学习系列 Hadoop+Spark+Zookeeper+HBase+Hive集群搭建 图文详解

目录 引言 目录 一、环境选择 1,集群机器安装图 2,配置说明 3,下载地址 二、集群的相关配置 1,主机名更改以及主机和IP做相关映射 2,ssh免登录 3,防火墙关闭 4,时间配置 5,快捷键设置...

董黎明
40分钟前
1
1
六元一个的私有博客系统,了解一下?

神说要有光,于是便有了光 写代码的,偶尔都想装点逼,想要自己写点博客。刚开始还能在各大社区写,比如说CSDN,开源中国,博客园什么的。但是越写就会越觉得,那些博客平台都不是自己想要的...

耒耒耒耒耒
45分钟前
1
0
maven环境隔离

一.maven项目环境根据实际情况进行隔离: 开发环境 dev 测试环境 beta 线上环境 prod 二.pom 配置: build节点 <build> <resources> <resource> <directory>src/......

imbiao
45分钟前
1
0
webrtc收包流程源码分析

版本: webrtc M59 收包流程: AsyncUDPSocket::OnReadEvent AllocationSequence::OnReadPacket HandleIncomingPacket UDPPort::OnReadPacket Connection::OnReadPacket P2PTransportChannel......

bill_shen
47分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部