文档章节

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
迪杰斯特拉(Dijkstra)算法描述与路径计算

1.迪杰斯特拉算法描述 迪杰斯特拉算法是基于LLDP(一种由IEEE802.1AB[11]定义的链路层发现协议)获取信息,是一个从顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特...

墨痕hz
2017/11/28
0
0
游戏中的人工智能之流场寻路

流场简介 流场,一般为网格图,网格中的每一个节点包含一个向量,该向量是物体在该位置时期望的速度。 流场寻路 利用流场的速度信息指导大量物体同时进行寻路。换句话说,如何生成可以寻路的...

RonTang
2016/04/20
0
0
迪杰斯特拉改进

在迪杰斯特拉基础上,增加两个限制,1.限制经过的节点个数。2.必须经过某些点。两个问题分开来都可以解决。第一个是在迪杰斯特拉算法上增加一个数组存储经过的边。第二个用贪心,求每一段的最...

watertiger
2017/05/04
41
0
基本算法——图算法之最短路径(Dijkstra)

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,针对的是非负权边,解决的是有向图中最短路径问题。迪杰...

安然若知
07/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

重磅!亚洲诚信实力斩获:“2018 DigiCert/Symantec 年度最佳创新合作伙伴”大奖

2018年11月13日-16日,全球顶级数字证书厂商,DigiCert/Symantec亚太区圆桌会议(Asia Partner Roundtable 2018)在日本大阪隆重召开。 亚洲诚信作为DigiCert/Symantec亚太区白金战略合作伙伴和...

亚洲诚信
28分钟前
2
0
始于阿里,回归社区:阿里8个项目进入CNCF云原生全景图

摘要: 一群技术理想主义者,与太平洋另一边的技术高手们正面PK,在这场躲不开的战役中,一起认真一把。 破土而出的生命力,源自理想主义者心底对技术的信念。 云原生技术正席卷全球,云原生...

阿里云官方博客
35分钟前
3
0
修改this指向(bind、call 和 apply)

一、bind bind 的其中一个用法就是:绑定函数,使其无论怎么样调用都用相同的 this 示例: var obj = { getThis: function() { console.log(this); }};obj.getThis()...

文文1
今天
1
0
WSL安装JDK8

下载地址 JDK_URL https://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html UNLIMITED_STRENGTH_URL https://www.oracle.com/technetwork/java/javase/down......

terwergreen
今天
4
0
sparkStreaming基本概念

概述 Spark Streaming 是 Spark Core API 的扩展, 它支持弹性的, 高吞吐的, 容错的实时数据流的处理. 数据可以通过多种数据源获取, 例如 Kafka, Flume, Kinesis 以及 TCP sockets, 也可以通过...

freeli
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部