在日常生活中,我们如果需要常常往返A地区和B地区之间,我们最希望知道的可能是从A地区到B地区间的众多路径中,那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。
用于解决最短路径问题的算法被称做“最短路径算法”, 有时被简称作“路径算法”。 最常用的路径算法有:Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。
Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解。本篇博客将详细介绍狄克斯特拉(Dijkstra算法)
Dijkstra算法思想
Dijkstra算法思想为:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只 有一个源点,以后每求得一条最短路径 , 就将 加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用 U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶 点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为 中间顶点的当前最短路径长度。
这些叙述性的思想看的人头晕,下面用例子来一步步讲解。
我们要使用到的图如下:
我们使用二维数组对其数据化:
#define INF 10000 //表示不可到达 #define MAXSIZE 7 //表示图的结点数 //邻接矩阵存储图的信息 int map[MAXSIZE][MAXSIZE]={ {0,4,6,6,INF,INF,INF}, {INF,0,1,INF,7,INF,INF}, {INF,INF,0,INF,6,4,INF}, {INF,INF,2,0,INF,5,INF}, {INF,INF,INF,INF,0,INF,6}, {INF,INF,INF,INF,1,0,8}, {INF,INF,INF,INF,INF,INF,0} };
定义多个数组来记录:
away[i]: 起点到顶点i的目前最短路径长度
path[]:保存最短路径
s[i]: 标记i顶点是否已找到最短路径,1表示已找到,代码中用的是already[]
画出Dijkstra算法步骤图如下:
理解了Dijkstra算法的步骤后,写出其代码为:
void Dijkstra(int v) { int away[MAXSIZE];//保存到各个点的最短距离 int path[MAXSIZE];//最短距离路径 int already[MAXSIZE]={0};//是否已经找到最短距离,1表示找到了,对应上图的s[] for(int i=0;i<MAXSIZE;i++) { away[i]=map[v][i];//获取权值 if(away[i]<INF)//存在路径为0 path[i]=0; else path[i]=-1;//不存在路径为-1 } already[v]=1;//把顶点v加入到找到数组里 //开始寻找最短距离 int min,ok; for(int i=0;i<MAXSIZE;i++) { min=INF; for(int k=0;k<MAXSIZE;k++) { if(already[k]==0&&away[k]<min)//找away里的最小值,且该顶点不在already里 { min=away[k]; ok=k;//记录最小的顶点 } } already[ok]=1;//把顶点ok加入到找到数组里 //修改away和path数组 for(int j=0;j<MAXSIZE;j++) { if(already[j]==0)//此结点还没有最短距离 { if(map[ok][j]<INF&&(away[ok]+map[ok][j])<away[j]) { away[j]=away[ok]+map[ok][j]; path[j]=ok;//修改path,修改过away权值的把path改为顶点值 } } } } }
得到path[]数组后,我们还要根据path的值来计算顶点0到各点的路径。
如我们要求顶点0到顶点6的路径:
步骤如下:
path[6]=4;
path[4]=5;
path[5]=2;
path[2]=1;
path[1]=0;(一旦值为0,则结束,且这个0不能算进去)
加上起点0(不是最后算出来那个0)和终点6,则其路径为0->1->2->5->4->6(倒叙),
最短路径为away[6]=16
计算路径的代码为:
for(int s=0;s<MAXSIZE;s++) { if(s!=v)//除去起点 { if(already[s]==1) { cout<<endl<<"从顶点"<<v<<"到顶点"<<s<<"的最小距离为: "<<away[s]<<" "<<"路径为: "; vector<int>temp; temp.insert(temp.begin(),s);//把终点插入 int ok=s; while(true) { ok=path[ok]; if(ok==0)//停止 break; temp.insert(temp.begin(),ok);//把起点插入 } temp.insert(temp.begin(),v);//把起点插入 for(int z=0;z<temp.size();z++) cout<<temp[z]<<" "; } else cout<<endl<<"从顶点"<<v<<"到顶点"<<s<<"不存在路径"<<endl; } }
至此,就完成了Dijkstra算法求最短路径的问题,主要是要理解Dijkstra算法的过程,特别是away[]和path[]
两个数组的变化。
附上源代码地址:https://github.com/longpo/algorithm/tree/master/Dijkstra
相关推荐
在本数据结构实验中,我们将探索“最短路径-Dijkstra-欧洲旅行”的概念。这个实验是基于Dijkstra算法,一种广泛用于寻找图中两点间最短路径的算法。在这个特定的场景下,我们假设有一个覆盖整个欧洲的铁路系统,每个...
Dijkstra算法是一种常用的图搜索算法,用于计算图中的一条最短路径。该算法的主要思想是从图的某个顶点出发,逐步扩展到其他顶点,直到找到目标顶点的最短路径。 在本节中,我们将详细讲述Dijkstra算法的实现过程,...
图的最短路径-Dijkstra算法 图的最短路径问题是图论领域中的一个基本问题,旨在寻找从给定源顶点到其它顶点的权最小路径。Dijkstra算法是一种常用的单源最短路径算法,用于解决带权有向图中的最短路径问题。 单源...
最短路径算法Dijkstra是图论中的一个经典算法,由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。该算法主要用于寻找带权重的有向或无向图中,从一个特定顶点到其他所有顶点的最短路径。Dijkstra算法的核心思想是...
总结起来,Dijkstra算法是解决最短路径问题的重要工具,其MATLAB实现使得算法的理解和应用变得更加便捷。通过理解算法原理并掌握MATLAB实现,我们可以更好地利用这一算法解决实际问题,特别是在图论和网络科学领域。
贪心算法之应用-单源最短路径-Dijkstra算法学习
**Dijkstra算法详解** ...总结来说,Dijkstra算法是解决图论中最短路径问题的利器,通过贪心策略逐步找到从起点到各个节点的最短路径。理解并熟练掌握Dijkstra算法对于理解和解决实际问题至关重要。
本问题中提到的“最短路径-欧洲游”是一个具体实例,通过解决这个问题,我们可以学习到如何运用Dijkstra算法来寻找图中的最短路径。 Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出的,主要用于...
Dijkstra算法的核心思想是贪心策略,即每次扩展当前已知最短路径的顶点,并更新其邻居节点的最短路径。算法以源节点为起始点,维护一个优先队列(通常用最小堆实现),存储待处理的顶点及其当前估计的最短路径长度。...
为了解决这一问题,徐辛超在论文《最短路径分析Dijkstra算法的优化实现》中提出了对Dijkstra算法的优化。该优化的关键在于,通过减少不必要的节点搜索,避免对已标识节点以外的节点进行重复计算,从而提高算法效率。...
"用Dijkstra算法求图中单源最短路径" Dijkstra算法是一种常用的图搜索算法,用于解决单源最短路径问题。单源最短路径问题是指从一个出发顶点到所有可达顶点的最短路径问题。Dijkstra算法的原理是通过将图中的每个...
最短路径的dijkstra算法-dijkstra.m 程序给出了求最短路径的dijkastra算法function [r_path, r_cost] = dijkstra % The Dijkstra's algorithm, Implemented by Yi Wang, 2005 % pathS: 所求最短路径的起点 % ...
java算法分析与设计之单源最短路径(Dijkstra算法)源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络...
### 计算最短路径树Dijkstra算法的改进 #### 概述 本文主要探讨了在现有的Dijkstra算法基础上进行的改进,旨在更好地适应网络寻径表刷新的需求,特别是针对OSPF(Open Shortest Path First)路由选择协议的应用...
该程序是我写的博客“一起talk C栗子吧(第五十四回:C语言实例--图的最短路径二)”的配套程序,共享给大家使用
并行最短路径算法Dijkstra。 为实现并行最短路径计算,我们必须要解决如下问题: (1)数据获取:利用随机函数生成大约2000个节点及其节点之间的距离。本程序使用邻接矩阵来存储带权有向图的信息。矩阵大小2000*2000...
总的来说,通过邻接矩阵和Dijkstra算法,我们可以有效地在图中找到最短路径,这对于网络路由、地理信息系统、交通规划等许多领域都有重要应用。在实际编程中,优化算法性能(例如使用 Fibonacci heap 或者 A* 搜索...
1. **Dijkstra算法**:Dijkstra算法是最常用的求解单源最短路径的算法,它保证了找到的路径是局部最优的,即每次选择当前未访问节点中距离源节点最近的一个。这种方法适用于边的权重非负的情况。 2. **Bellman-Ford...