该算法由荷兰的一个牛人计算机科学家Edsger Wybe Dijkstra在1956年发现。
这套算法主要解决计算从一个点到其它的点的最短距离,而不是Floyd-Warshall算法的任意两点距离。
如图,现要计算出,从1号点到其它各点的最短距离,首先我还是转化成矩阵
由此可见1号点到其它点的初始距离为:
0 1 12 ∞ ∞ ∞
很明显2号点是离1号点最近的点,那么1号点到2号点的最短距离肯定就是直达了。那我就将2号点作为“换乘点”,来计算下距离:
0 1 10 4 ∞ ∞
这个过程有个专业术语“松弛”。2号点我也已经用了,那么4号点是离1号最近的点了,那再用它来松弛下:
0 1 8 4 17 19
接下来,就不费话了,继续松弛吧,直到所有点都用来松过。
这就是Dijkstra算法的思想,略屌,略屌!
现在用C来实现下:
#include <stdio.h> int main() { int a[10][10], dis[10], book[10], n, m, t1, t2, t3, i, j, k, min, u; int inf = 99999999;//这里定义的正无穷 //读入nm,n为顶点数,m为边的条数 scanf("%d %d", &n, &m); //初始化矩阵 for (i = 1; i <= n; i++) for(j = 1; j <= n; j++) if(i == j)a[i][j] = 0; else a[i][j] = inf; //读入边 for(i = 1; i <= m; i++) { scanf("%d %d %d", &t1, &t2, &t3); a[t1][t2] = t3; } //初始化dis,这里存的是从1号顶点到其它顶点的初始距离 for(i = 1; i <= n; i++) dis[i] = a[1][i]; //初始化book,标记某个点是否已经“松弛”过了 for(i = 1; i <= n; i++) book[i] = 0; book[1] = 1;//从1到1的距离是0,为确定距离 //Dijkstra算法核心代码 for(i = 2; i <= n; i++)//这里从2开始,因为1号到1号不用算了。下面也一样 { min = inf; //找到离i最近的顶点 for(j = 2; j <= n; j++) { if(book[j] == 0 && dis[j] < min) { min = dis[j]; u = j; } } book[u] = 1; for(k = 1; k <= n; k++) { if(a[u][k] < inf && dis[k] > dis[u] + a[u][k]) { dis[k] = dis[u] + a[u][k]; } } } for(i = 1; i <= n; i++) printf("%d \n", dis[i]); return 0; }
输入:
6 9 1 2 1 1 3 12 2 3 9 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4
得到结果:
0 1 8 4 13 17
这套程序的时间复杂度为O(N2)。想想有什么办法还能优化它。
相关推荐
本程序是用matlab语言实现,Dijkstra算法主要用来寻找任意两点间的最短路径
dijkstra算法的R语言实现。输入为邻接矩阵和权重矩阵。如果没有权重,则认为权重矩阵为邻接矩阵。输出为从源节点到网络其他节点的最短距离和最短路径。如果有多条最短路,可以选择同时输出多条路。
本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题。分享给大家供大家参考,具体如下: 这里继续前面一篇《Python基于Floyd算法求解最短路径距离问题》的内容,这里要做的是Dijkstra算法,与Floyd...
利用Dijkstra算法来求解顶点之间最短路径
Dijkstra算法算是贪⼼思想实现的,⾸先把起点到所有点的距离存下来找个最短的,然后松弛⼀次再找出最短的,所谓的松弛操作就是,遍历⼀遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,...
# Python Dijkstra Algorithm 迪杰斯特拉算法 最短路径算法示例代码 ...程序将输出从起始节点到其他节点的最短距离。这些结果将在终端中显示。 Shortest distances from node A A : 0 B : 1 C : 3 D : 4
求解一个最短路径问题程序,可以参考一下求一个Dijkstra优化算法! 谢谢了 目的是求给定两点之间的最短距离 或者改一下我的程序也行
本文实例讲述了PHP实现的迪科斯彻(Dijkstra)最短路径算法。分享给大家供大家参考,具体如下: 一、待解决问题 单源最短路径问题,在给定有向图中求一个顶点(单源顶点)到其他所有顶点的最短路径问题。在下图中,每...
带权图的多种算法(有向图,无向图,Dijkstra算法,到每个顶点的最短距离,佛洛依德算法(Floyd),找出每对顶点的最短路径,带权重无向图最小生成树,prim算法,Kruskal算法求最小生成树)java实现, 有注释,简单...
算法这么课程的结课论文,以最短路径算法为例描述贪心算法
在地图上找到从起始节点到结束节点的最短路径和距离** 2. 找出地图上从起始节点到所有其他节点的最短路径和距离** **地图应由节点和段组成,例如: 1.节点的格式为[ID XY]或[ID XYZ](ID为整数,X,Y,Z代表位置坐标...
输入各结点构成的邻接矩阵及开始结点,计算出该节点到其他各节点之间的最短距离。也可计算某一开始结点到指定结点的最短距离。
戴克斯特拉算法(Dijkstra’s algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向...对于不含负权的有向图,Dijkstra算法是目前已知的最快的单源最短路径算法。
该程序是我写的博客“一起talk C栗子吧(第五十四回:C语言实例--图的最短路径二)”的配套程序,共享给大家使用
用C++和STL编写的dijkstra算法,计算非负边两点之间的最短距离。
为了实现这一过程,算法通常需要一个距离数组来记录从源点到各个顶点的最短距离,以及一个标记数组来记录各个顶点是否已经被处理过。在每次迭代中,算法会从距离数组中选择一个距离最小的未处理顶点,然后更新与该...
SPFA算法 此处为SPFA算法详解 用dis数组记录源点到有向图上任意一点...此处为Dijkstra算法详解 清除所有点的标号; 设d[0]=0,其他d[i]=INF;//INF是一个很大的值,用来替代正无穷 循环n次 { 在所有未标号结点中,
Dijkstra算法的Matlab程序,用于求各点之间的最短路距离。这里提供了一个可以通用的matlab 程序代码。
Dijkstra 算法,以武汉大学范围(文理学部,工学部,信息学部)为例,设计两种模式—地名输入模式和自由选点模式,并根据输入地名或选择点位自动规划出起点与终点间的最短路径在地图上予以显示,同时显示路径转点和...
1.版本:matlab2014/2019a/...擅长智能优化算法、神经网络预测、信号处理、元胞自动机等多种领域的算法仿真实验,更多仿真源码、数据集定制私信+。 %% 开发者:Matlab科研助手 %% 更多咨询关注天天Matlab微信公众号