文档章节

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

htq
 htq
发布于 2016/07/26 09:40
字数 877
阅读 43
收藏 0
点赞 0
评论 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
java实现Dijkstra算法求最短路径

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra一般的表述通常有两...

zaizai_loong
2013/09/08
0
2
数学:Dijkstra算法

一.最短路径的最优子结构性质 该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的...

pricker
2015/09/12
112
0
求两点之间最短路径-Dijkstra算法

Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dij...

雲霏霏
2015/02/26
0
0
像名字一样容易忘记的Dijkstra

Dijkstra算法是经典的求解一个顶点到其他顶点的最短距离的算法。每次学习的时候总是觉得思路简单明了,但每当要用到时,就忘记了实现的细节。归根结底还是应用的少。相信做地图导航的应该对其...

dugangabc
2016/02/06
0
0
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

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

索隆
2011/12/03
0
0
最短路径问题---Dijkstra算法详解

前言 Nobody can go back and start a new beginning,but anyone can start today and make a new ending. Name:Willam Time:2017/3/8 1、最短路径问题介绍 问题解释: 从图中的某个顶点出发......

qq_35644234
2017/03/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

大数据教程(2.13):keepalived+nginx(多主多活)高可用集群搭建教程【自动化脚本】

上一章节博主为大家介绍了目前大型互联网项目的keepalived+nginx(主备)高可用系统架构体系,相信大家应该看了博主的文章对keepalived/nginx技术已经有一定的了解,在本节博主将为大家分享k...

em_aaron
7分钟前
0
0
Git 2.18版本发布:支持Git协议v2,提升性能

在最新的官方 Git 客户端正式版2.18中添加了对 Git wire 协议 v2 的支持,并引入了一些性能与 UI 改进的新特性。在 Git 的核心团队成员 Brandon Williams 公开宣布这一消息前几周,Git 协议 ...

六库科技
12分钟前
0
0
Java8新特性之接口

在JDK8以前,我们定义接口类中,方法都是抽象的,并且不能存在静态方法。所有的方法命名规则基本上都是 public [返回类型] [方法名](参数params) throws [异常类型] {}。 JDK8为接口的定义带...

developlee的潇洒人生
50分钟前
0
0
aop + annotation 实现统一日志记录

aop + annotation 实现统一日志记录 在开发中,我们可能需要记录异常日志。由于异常比较分散,每个 service 方法都可能发生异常,如果我们都去做处理,会出现很多重复编码,也不好维护。这种...

长安一梦
今天
2
0
将博客搬至CSDN

AHUSKY
今天
1
0
Python web框架Django学习(1)

1.Django简介 (1)Python下有许多款不同的 Web 框架。Django是重量级选手中最有代表性的一位。许多成功的网站和APP都基于Django。Django是一个开放源代码的Web应用框架,由Python写成。 (2...

十年磨一剑3344
今天
0
0
Databook-数据之书

Databook-数据之书 用于数据分析的Jupyter Notebooks。 不需购买服务器,快速开始自己的数据分析过程。 源码:https://github.com/openthings/databook 作者:openthings,https://github.co...

openthings
今天
7
0
Python PIPEs

https://www.python-course.eu/pipes.php https://www.tutorialspoint.com/python/os_pipe.htm

zungyiu
今天
1
0
gRPC学习笔记

gRPC编程流程 1. proto文件定义 proto文件用于定义需要通过gRPC生成的接口,可以理解为接口定义文档 2. 通过构建工具生成服务基类代码-Maven或Gradle 3. 服务端开发 服务端实现类须实现通过构...

OSC_fly
今天
0
0
Docker Mac (三) Dockerfile 及命令

Dockerfile 最近学习docker的时候,遇到一件怪事,关于docker镜像可能会被破坏,还不知道它会有此措施 所以需要了解构建Dockerfile的正确方法 Dockerfile是由一系列命令和参数构成的脚本,这些命...

___大侠
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部