文档章节

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

htq
 htq
发布于 2016/07/26 09:40
字数 877
阅读 57
收藏 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 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,针对的是非负权边,解决的是有向图中最短路径问题。迪杰...

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

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

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

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

RonTang
2016/04/20
0
0
java实现Dijkstra算法求最短路径

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

zaizai_loong
2013/09/08
0
2

没有更多内容

加载失败,请刷新页面

加载更多

如何在 Linux 系统查询机器最近重启时间

在你的 Linux 或类 UNIX 系统中,你是如何查询系统上次重新启动的日期和时间?怎样显示系统关机的日期和时间? last 命令不仅可以按照时间从近到远的顺序列出该会话的特定用户、终端和主机名...

来来来来来
57分钟前
1
0
Redis协议是什么样的

前言 我们用过很多redis的客户端,有没有相过自己撸一个redis客户端? 其实很简单,基于socket,监听6379端口,解析数据就可以了。 redis协议 解析数据的过程主要依赖于redis的协议了。 我们...

春哥大魔王的博客
今天
3
0
乱入Linux界的我是如何学习的

欢迎来到建哥学Linux,咳!咳!咳!开个玩笑哈,我是一个IT男,IT界的入门选手,正在学习Linux。 在之前,一直想进军IT界,学习IT技术,但是苦于没有人指导,也不知道学什么,最开始我自己在...

linuxCool
今天
3
0
携程Apollo统一配置中心的搭建和使用(java)

一.Apollo配置中心介绍 1、What is Apollo 1.1 Apollo简介 Apollo(阿波罗)是携程框架部门研发的开源配置管理中心,能够集中化管理应用不同环境、不同集群的配置,配置修改后能够实时推送到...

morpheusWB
今天
2
0
远程获得的有趣的linux命令

使用这些工具从远程了解天气、阅读资料等。 我们即将结束为期 24 天的 Linux 命令行玩具日历。希望你有一直在看,如果没有,请回到开始,从头看过来。你会发现 Linux 终端有很多游戏、消遣和...

Linux就该这么学
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部