文档章节

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;
}


© 著作权归作者所有

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

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

索隆
2011/12/03
0
0
游戏中的人工智能之流场寻路

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

RonTang
2016/04/20
0
0
迪杰斯特拉(Dijkstra)算法描述与路径计算

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

墨痕hz
2017/11/28
0
0
迪杰斯特拉改进

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

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

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

安然若知
2018/07/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

vue 对对象的属性进行修改时,不能渲染页面 vue.$set()

我在vue里的方法里给一个对象添加某个属性时,我console.log出来的是已经更改的object ,但是页面始终没有变化 原因如下: **受现代 JavaScript 的限制 (而且 Object.observe 也已经被废弃),...

Js_Mei
今天
2
0
开始看《Java学习笔记》

虽然书买了很久,但一直没看。这其中也写过一些Java程序,但都是基于IDE的帮助和对C#的理解来写的,感觉不踏实。 林信良的书写得蛮好的,能够帮助打好基础,看得出作者是比较用心的。 第1章概...

max佩恩
昨天
12
0
Redux 三大原则

1.单一数据源 在传统的MVC架构中,我们可以根据需要创建无数个Model,而Model之间可以互相监听、触发事件甚至循环或嵌套触发事件,这些在Redux中都是不被允许的。 因为在Redux的思想里,一个...

wenxingjun
昨天
8
0
跟我学Spring Cloud(Finchley版)-12-微服务容错三板斧

至此,我们已实现服务发现、负载均衡,同时,使用Feign也实现了良好的远程调用——我们的代码是可读、可维护的。理论上,我们现在已经能构建一个不错的分布式应用了,但微服务之间是通过网络...

周立_ITMuch
昨天
5
0
XML

学习目标  能够说出XML的作用  能够编写XML文档声明  能够编写符合语法的XML  能够通过DTD约束编写XML文档  能够通过Schema约束编写XML文档  能够通过Dom4j解析XML文档 第1章 xm...

stars永恒
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部