文档章节

【图的最短路径】迪杰斯特拉算法求图的最短路径

htq
 htq
发布于 2016/07/26 09:40
字数 877
阅读 48
收藏 0

要求:求带权有向图中某一结点到其他结点的最短路径。

用迪杰斯特拉算法求解,迪杰斯特拉算法书上的描述如下:
对于图G=(V,{E}),将图中的顶点归为两组:
第一组S:已求出的最短路径的终点集合(开始为{v0})
第二组:V-S尚未求出的最短路径的顶点的集合(开始为V-{v0}的全部顶点)
该算法将最短路径长度的递增顺序逐个将第二组中的顶点加入到第一组中,直到所有的顶点都被加入到第一组顶点集S为止。
这是书上的描述,比较抽象,本人将自己的理解与大家分享如下:

思路:

 1首先初始化工作:三个准备数组path保存从v到i的路径,dist保存从v到i的最短路径,visit保存当前访问点是  已加入G中

 2 初始化:若dist不为INFINITY则将v加入到path[i]中,将visit置false,将dist置能直达的距离

 3然后将处顶点v外的其余n个顶点加入G中,所以应采用for循环n-1次,每次选取dist最小的顶点k加入G中

 4加入后得重新求dist,因为k加入后可作中转站供原本不能走通的路径走通,一旦第i个顶点的dist重新修改后, 得将顶点k加入到i的path路径中


基于以上步骤代码如下:
#include<iostream>
using namespace std;
const int INFINITY=23678;
const int M=3;
/*typedef struct G
{
int ver[M];
int arc[M][M];
int vernum,arcnum;
}G;*/
void path_(int n,int g[][M],int v)//为了简化过程,专注算法本质,将图的数据结构直接用数组加定点数来代替
{
int dist[M],path[M],visit[M];
int k;//k用来保存每次选出的最小的路径的顶点的下标
for(int i=0;i<n;i++)
{
dist[i]=g[v][i];
if(dist[i]==INFINITY)
{
path[i]=0;
}
else
{
path[i]=v;
}
visit[i]=false;//刚开始所有的顶点都未加入G中
}
visit[v]=true;
for(int t=1;t<n-1;t++)
{
int min=INFINITY;
for(int i=0;i<n;i++)
{
if(!visit[i]&&dist[i]<INFINITY)
{
min=dist[i];
k=i;
}
}
if(min==INFINITY)
return;
visit[k]=true;//将顶点k加入已确定从v到i的最短路径的集合G中
for(int i=0;i<n;i++)//因为已将k加入到集合G中,所以k可以作为中转站来供其它原本不能直达的顶点可以走通
//所以必须将所有的(注意是所有的,这点类似图的DFS算法)顶点的最短路径进行修改
{
if(!visit[i]&&dist[k]+g[k][i]<dist[i])
{
dist[i]=dist[k]+g[k][i];
path[i]=k;//注意此时不要忘了,一旦修正则需将该中转点加入到该顶点的路径中
}

}
}
for(int i=0;i<n;i++)
{
if(dist[i]==INFINITY)
{
cout<<"该顶点无最短路径"<<endl;

}
else
{
int pre=i;
do{
printf("%d<--",pre);
pre=path[pre];//注意这种技巧,类似链表,一环扣一环
}while(pre!=v);
printf("%d",v);
printf("\n");
}
}
}
void main()
{
int vernum=3;
int g[M][M]={{0,4,INFINITY},{12,0,5},{6,INFINITY,0}};
path_(vernum,g,2);//求每个顶点到顶点2的最短路径。

}


程序运行结果如下:

注:x<--y表示从y到x的最短路径,上图输出的是给定数组g[M][N]中的每个顶点到顶点2的最短路径。

本文转载自:http://blog.csdn.net/htq__/article/details/50856032

共有 人打赏支持
htq

htq

粉丝 19
博文 67
码字总数 1007
作品 3
武汉
迪杰斯特拉(Dijkstra)算法描述与路径计算

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

墨痕hz
2017/11/28
0
0
基本算法——图算法之最短路径(Dijkstra)

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

安然若知
07/13
0
0
迪杰斯特拉改进

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

watertiger
2017/05/04
41
0
游戏中的人工智能之流场寻路

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

RonTang
2016/04/20
0
0
判断某节点是否和其他节点联通并计算时延 Network Delay Time

问题: There are network nodes, labelled to . Given , a list of travel times as directed edges , where is the source node, is the target node, and is the time it takes for a sig......

叶枫啦啦
01/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

搬瓦工镜像站bwh1.net被DNS污染,国内打不开搬瓦工官网

今天下午(2018年10月17日),继搬瓦工主域名bandwagonhost.com被污染后,这个国内的镜像地址bwh1.net也被墙了。那么目前应该怎么访问搬瓦工官网呢? 消息来源:搬瓦工优惠网->搬瓦工镜像站b...

flyzy2005
41分钟前
1
0
SpringBoot自动配置

本篇介绍下,如何通过springboot的自动配置,将公司项目内的依赖jar,不需要扫描路径,依赖jar的情况下,就能将jar内配置了@configuration注解的类,创建到IOC里面 介绍下开发环境 JDK版本1.8 spr...

贺小五
今天
3
0
命令行新建Maven多项目

参考地址 # DgroupId 可以理解为包名# DartifactId 可以理解为项目名mvn archetype:generate -DgroupId=cn.modfun -DartifactId=scaffold -DarchetypeArtifactId=maven-archetype-quickst......

阿白
今天
1
0
OSChina 周四乱弹 —— 上帝对我单身年限的惩罚越来越长了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @达尔文:分享张卫健的单曲《身体健康》 《身体健康》- 张卫健 手机党少年们想听歌,请使劲儿戳(这里) 昨天是重阳节咯, 可惜小小编辑总是晚...

小小编辑
今天
12
1
django rest framework 外键序列化方法与问题总结

django rest framework 外键序列化方法与问题总结 当借口中需要出现一对多关系的时候,我们可以用rest_framwork的序列化功能来处理,代码如下. # models.pyfrom django.db import modelscl...

_Change_
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部