-
2021-04-19 02:17:11
%单源点最短路径Dijkstra算法实现
function [d index1 index2] = Dijkf(a)
% a 表示图的权值矩阵
% d 表示所求最短路的权和
% index1 表示标号顶点顺序
% index2 表示标号顶点索引
%参数初始化
M= max(max(a));
pb(1:length(a))= 0; % 标记向量,表明是否已进入S集合
pb(1)= 1;
index1= 1;
index2= ones(1,length(a));
d(1:length(a))= M; % d矩阵所有元素都初始化为最大权值
d(1)= 0; % 以v1点为源点
temp= 1;
% 更新l(v),同时记录顶点顺序和顶点索引
while sum(pb)
tb= find(pb==0);
d(tb)= min(d(tb),d(temp)+a(temp,tb)); % 更新l(v)
tmpb= find(d(tb)==min(d(tb))); % 找出min(l(v))
temp= tb(tmpb(1));
pb(temp)= 1;
index1= [index1,temp]; % 记录标号顺序
index= index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2
index= index(1);
end % if结束
index2(temp)= index; % 记录标号索引
end % while结束
end
% Dijkf函数结束
取消
评论
更多相关内容 -
Dijkstra算法(matlab实现)
2021-03-17 07:37:02Dijkstra算法 Dijkstra算法主要是用来解决单源点最短路径问题。 该算法的思路如下: 在一个带非负权值的图G=(V,E)中,把顶点集V分为两组。 S:已求出最短路径的顶点的集合,初始时集合S中只有源点s。 V-S:尚未...Dijkstra算法
Dijkstra算法主要是用来解决单源点最短路径问题。
该算法的思路如下:- 在一个带非负权值的图G=(V,E)中,把顶点集V分为两组。
- S:已求出最短路径的顶点的集合,初始时集合S中只有源点s。
- V-S:尚未确定最短路径的顶点集合,将V-S中顶点按最短路径递增的次序加入S中。
function [mydistance,mypath]=mydijkstra(a,sb,db); %输入:a——邻接矩阵;a(i,j)——i到j之间的距离,可以是有向的 %sb——起点的标号,db——终点的标号 %输出:mydistance——最短路的距离,mypath——最短路的路径 n=size(a,1);visited(1:0)=0; distance(1:n)=inf;distance(sb)=0; %起点到各顶点距离的初始化 visited(sb)=1;u=sb; %u为最新的S集合顶点 parent(1:0)=0; %前驱顶点的初始化 for i=1:n-1 id=find(visited==0); %查找V-S集合的顶点 for v=id if a(u,v)+distance(u)<distance(v) distance(v)=distance(u)+a(u,v); %修改标号值 parent(v)=u; end end temp=distance; temp(visited==1)=inf; %已标号点的距离换成无穷大 [t,u]=min(temp); %找标号值最小的顶点 visited(u)=1; %标记已经标号的顶点 end mypath=[]; if parent(db)~=0 %如果存在路! t=db;mypath=[db]; while t~=sb P=parent(t); mypath=[P mypath]; t=P; end end mydistance=distance(db);
-
Dijkstra算法的原理及c语言实现
2021-12-31 17:14:291)Dijkstra算法是典型最短路径算法,用于计算单源点的最短路径问题,即求无向加权图G=<V,E,W>中一个节点到其他节点的最短路径。实际上就是根据网络的链路代价,采用广度优先搜索的思想,以起始点为中心向外...源码链接: https://blog.csdn.net/qq_44394952/article/details/122587738.
1.课程设计要求
1)输入必要参数,包括:结点个数、节点间路径长度、给定节点;
2)输出给定节点到其它各节点的最短路径、径长;
3)节点间路径长度用矩阵形式表示;
4)可使用MATLAB 或者其他语言进行设计;
5)设计图形化界面展示本人的工作;2.基本原理
1)Dijkstra算法是典型最短路径算法,用于计算单源点的最短路径问题,即求无向加权图G=<V,E,W>中一个节点到其他节点的最短路径。实际上就是根据网络的链路代价,采用广度优先搜索的思想,以起始点为中心向外层层扩展,直到扩展到终点为止来计算一对节点之间的最小代价路径。最短路径问题是图论中研究的一个重要课题,不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、线路容量等。例如,城市交通中出行者选择出行路径,通信网络中的最可靠路径、最大容量路径问题等,都可以转化为最短路径问题。
2)操作步骤:
Step1:通过Dijkstra算法计算无向加权图G中的最短路径时,需要指定起点s。
Step2:引进两个集合S和U。S的作用是记录已求出最短路径的顶点以及相
应的最短路径长度,初始时被赋为 0。U记录还未求出最短路径的顶点
以及该顶点到起点s的距离,需要注意的是,U中顶点v的距离为(s,v)
的长度,如果s存在能直接到达v的边(s,v),则v的距离为(s, v);
如果s不存在能直接到达v的边(s,v),则v的距离为∞。
Step3:初始时,S中只有起点s,U中是除s之外的顶点。
Step4:从U中找出路径最短的顶点k,并将其加入到S中;接着,从U中移
除顶点k并更新U中的顶点和顶点对应的路径,之所以更新U中顶点
的距离,是由于确定了k是求出最短路径的顶点,从而可以利用k来更
新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离,则(s,v)
的距离更新为(s,k)+(k,v)的距离
Step5:重复操作步骤4),直到遍历完所有结点。
Dijkstra 每次循环都可以确定一个顶点的最短路径,故程序需要循环 n-1 次。
3)图解举例:
以下图为例,以v0为起始结点,对Dijkstra进行算法原理演示
Step1:将v0放入集合S,从v0开始,
找到与其邻接的点:v1、v2、v3,更新D(v1)、D(v2)、D(v3);
v0不与v4,v5,v6邻接,故D(v4)、D(v5)、D(v6)为∞。
在D(v)中找到最小值为1,其顶点为v1,
即此时已找到 v0到v1的最短路径为v0→v1。
Step2:将v1放入集合S,从v1开始,继续更新D(v):
v1与v2不邻接,不更新;
v1与v3不邻接,不更新;
v1与v4不邻接,不更新;
v1与v5邻接,v0→v1→v5的路径为7比D(v5)=∞小,故更新D(v5) ;
v1与v6不邻接,不更新。
在D(v)中找到最小值为2,其顶点为v2,
即此时又找到v0到v2的最短路径为v0→v2。
Step3:将v2放入集合S,从v2开始,继续更新D(v):
v2与v3不邻接,不更新;
v2与v4邻接,v0→v2→v4的路径为7比D(v4)=∞小,故更新D(v4) ;
v2与v5邻接,v0→v2→v5的路径为6比D(v5)=7小,故更新D(v5) ;
v2与v6不邻接,不更新;
在D(v)中找到最小值为3,其顶点为v3,
即此时又找到v0到v3的最短路径为v0→v3。
Step4:将v3放入集合S,从v3开始,继续更新D(v):
v3与v4邻接,v0→v3→v4的路径为7等于D(v4)=7,故不更新;
v3与v5不邻接,不更新;
v3与v6不邻接,不更新;
在D(v)中找到最小值为6,其顶点为v5,
即此时又找到v0到v5的最短路径为v0→v2→v5。
Step5:将v5放入集合S,从v5开始,继续更新D(v):
v5与v4不邻接,不更新;
v5与v6邻接,v0→v2→v5→v6的路径为14比D(v6)=∞小,故更新D(v6) ;
在D(v)中找到最小值为7,其顶点为v4,
即此时又找到v0到v4的最短路径为v0→v2→v4。
Step6:将v4放入集合S,从v4开始,继续更新D(v):
V4与v6邻接,v0→v2→v4→v6的路径为14等于D(v6)=14,故不更新;
在D(v)中找到最小值为14,其顶点为v6,
即此时又找到v0到v6的最短路径为v0→v2→v4→v6。
Step7:将v6放入集合S,所有点都已找到,停止。3.仿真程序代码及分析
链接: https://blog.csdn.net/qq_44394952/article/details/122587738.
4.仿真结果及分析
输入结点数量、路径数量并依次输入每两个相连结点及其之间的路径长度:
输出结点间路径长度的矩阵
功能1:输入起始结点和目的结点,输出路径和距离
功能2:输出以v0为起始结点,其余各点为目的结点的全部路径和距离
通过测试发现c语言编程实现的结果与计算结果一致。
综上,通过c语言编程主要实现了两个功能:一是输入起始结点和目的结点,输出路径和距离;二是输出以v0为起始结点,其余各结点为目的结点的全部路径和距离。同时,c语言编程实现的实现因为可以输入结点数量、路径数量及每两个相连结点及其之间的路径长度,从而更具有普适性,不限制于某一给定的无向加权图。 -
Dijkstra算法C语言实现(附图解)
2020-05-10 20:28:23Dijkstra算法: 问题:给定一个带权图G=(V,E,w),找到从给定源点u0到其他各点的最短路径。 绿色顶点表示源点到该顶点的距离已确定 蓝色顶点表示要加入集合S的顶点 {dis,v},v表示前驱动点,dis表示源点到该顶点的最短...Dijkstra算法:
问题:给定一个带权图G=(V,E,w),找到从给定源点u0到其他各点的最短路径。
Step:
求带权图G(V,E)的点v0到其他各点的最短路径;
1.初始时,S={v0},U={v1,v1…vn};点v0到其他点的最短距离为<v0,vi>(i=1,2,3…n)的权;将v0到其他各点vi的最短路径中vi的前驱动点初始化为v0;
2,从U中选取u,使得当前v0到u的最短路径的距离小于v0到U中其他各点的最短路径的距离,将u加入S,并将u从U中删除
3,遍历每个在U中的点s,如果以u为中介点的最短路径的距离小于当前存储的距离,更新从v0到s的最短路径的距离,并将v0到s的最短路径的s的前驱动点更新为u;
4,重复2,3直到U为空;
绿色顶点表示源点到该顶点的距离已确定 蓝色顶点表示要加入集合S的顶点 {dis,v},v表示前驱动点,dis表示源点到该顶点的最短距离
代码:#include <stdio.h> #define INF 10000000 #define MaxSize 50 int graph[MaxSize][MaxSize]; //MaxSize为最大顶点数 int dis[MaxSize]; //dis[i]为源点到顶点i的最短距离 int visit[MaxSize]; //visit[i]标记顶点i的最短路径是否已求出visit[i] == 1表示已求出 int prevetrix[MaxSize]; //前驱动点 void dij(int n) { int count = 0; //count是已求出最短路径的顶点数目 visit[0] = 1; prevetrix[0] = 0; count++; for (int i = 1; i < n; i++) //初始化 { dis[i] = graph[0][i]; prevetrix[i] = 0; } while (count < n) { int min = INF, target_index; for (int i = 1; i < n; i++) { if (visit[i] == 0 && min > dis[i]) //找到距离源点最短的顶点target_index { min = dis[i]; target_index = i; } } visit[target_index] = 1; count++; for (int i = 1; i < n; i++) { if (visit[i] == 0 && dis[target_index] + graph[target_index][i] < dis[i]) //更新 { dis[i] = dis[target_index] + graph[target_index][i]; prevetrix[i] = target_index; } } } } int main() { int n, m; scanf("%d %d", &n, &m); //n为顶点数,m为边数 int a, b, w, path[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { graph[i][j] = INF; } } for (int i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &w); //a为起始点,b为终点,w为边a->b的权重 graph[a][b] = w; } dij(n); printf("\n\n"); for (int i = 1; i < n; i++) { if (dis[i] == INF) { printf("顶点0到顶点%d没有最短路径\n", i); } else { printf("顶点0到顶点%d有长为%d的最短路径:", i,dis[i]); int cur = i, index = 0; path[index] = cur; while (1) { path[index + 1] = prevetrix[path[index]]; if (path[index + 1] == 0) break; index++; } for (int j = index + 1; j > 0; j--) { printf("%d->", path[j]); } printf("%d\n", path[0]); } } }
输入: 6 8 0 2 10 0 4 30 0 5 100 1 2 5 2 3 50 3 5 10 4 5 60 4 3 20 输出: 顶点0到顶点1没有最短路径 顶点0到顶点2有长为10的最短路径:0->2 顶点0到顶点3有长为50的最短路径:0->4->3 顶点0到顶点4有长为30的最短路径:0->4 顶点0到顶点5有长为60的最短路径:0->4->3->5
注意:diskstra算法只能求边权值为非负值的情况
-
计算机网络实验4 编程实现路由算法
2022-03-20 20:44:591)实验目的: 运用各种编程语言实现基于 Dijkstra 算法的路由软件。。 ...1.选择合适的编程语言编程实现基于 Dijkstra 算法的路由软件。 2.输入不同的网络拓扑和链路代价测试和验证自己的路由软件 -
最短路径——Dijkstra算法(C语言实现)
2020-11-21 12:04:55最短路径(Dijkstar算法) 基本概念: 1)最短路径:非带权图——边数最少的路径;...算法:Dijkstra算法 输入:有向网图 G=(V,E) 源点 v 输出:从 v 到其他“所有顶点”的最短路径 1. 初始化:集合S = {v}; -
最短路径 Dijkstra算法的Matlab代码实现
2020-09-11 09:29:25% 利用dijkstra算法计算两点间的最短路径 % A:邻接矩阵 % strat:起点编号 % dest:终点编号 % path:最短路径索引 % distence:最短路径下的距离值 function [dist,path] = dijkstra(A,start,dest) % 测试数据 A =... -
使用Matlab、Python两种语言实现Dijkstra算法
2021-05-11 15:08:37使用Matlab、Python两种语言实现Dijkstra算法 迪杰斯特拉算法(Dijkstra algorithm)是一种采用贪心算法策略的经典算法,由荷兰计算机科学家狄克斯特拉提出,用于解决(有向或无向)带权图中最短路径问题。迪杰斯特拉... -
计算机网络课程实验4——编程实现路由算法(迪杰斯特拉算法)
2022-02-04 14:26:57实验步骤: 1, 选择合适的编程语言编程实现基于 Dijkstra 算法的路由软件。 输入不同的网络拓扑和链路代价测试和验证自己的路由软件。 实验代码部分如下(python): def generate_matrix(): M = 1E100 matrix = ... -
Dijkstra算法及其实现
2020-06-09 13:53:39之所以需要约定例如取检验数 σi\sigma_iσi 最大的变量为入基变量,主要是为了在处理自变量非常多的优化问题时,易于编程。 从而我又意识到,运筹是一门与实际联系非常紧密的学科,所以算法的时间复杂度也应该是 -
最短路径算法——Dijkstra算法——python3实现
2018-07-03 10:28:21本文参考来自数据结构与算法分析 java语言描述。 问题描述 问题分析 实现过程 如何使用数据变化表 问题描述 现有一个有向赋权图。如下图所示: 问题:根据每条边的权值,求出从起点s到其他每个顶点的最短... -
第5-3课:Dijkstra 算法
2020-09-22 12:17:19Dijkstra 算法是有中文名字的,一般叫做“迪杰斯特拉算法”,该算法是求解单源最短路径问题的经典算法,算不上高效,但确实是最简单的算法。Dijkstra 算法并不难,很多算法书都有详细的说明,但是这些书基本上都是对... -
网络原理实验报告(Dijkstra)
2021-03-13 00:37:24计算机网络原理课程实验Dijkstra算法的实验报告10 update D(v) for all v adjacent to w and not in N: 11 D(v) = min( D(v), D(w) + c(w,v) )12 /* new cost to v is either old cost to v or known 13 shortest ... -
【算法设计与分析】最短路径dijkstra算法和bellman-ford算法
2019-01-03 20:57:42文章目录一、实验内容1、 Dijkstra算法求最短路径。2、Bellman-ford算法求最短路径二、理论准备1、 Dijkstra算法2、bellman-ford算法3、 两个算法的使用环境。三、实验环境四、实验过程1、Dijkstra算法2、bellman-... -
Dijkstra算法
2022-05-15 07:26:30Dijkstra 算法,是由荷兰计算机科学家 Edsger Wybe Dijkstra 在1956年发现的算法,戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。Dijkstra 算法原始版本仅适用于找到两个顶点之间的最短... -
Python、C/C++混编实现最短路径可视化—Dijkstra算法
2019-01-12 05:57:08本文讲述的是主要是运用C/C++语言Dijkstra算法来完成交通图的存储、图中任一顶点到其余任意一顶点间的最短路径问题,并利用Python中的复杂网络分析库Networkx来绘制有向图以实现最短路径的可视化。 -
【历史上的今天】5 月 11 日:Dijkstra 算法开发者诞生;电子表格软件的开山鼻祖;机器狗 AIBO 问世
2022-05-11 12:42:375 月 11 日,历史上的今天,最短路径算法的开发者 Edsger W. Dijkstra 出生;“VisiCalc”首次公开演示;索尼推出了机器狗 AIBO。 -
迪杰斯特拉(Dijkstra)算法详解
2019-03-22 12:37:34D就是A点到D点的最最短路径,可是计算机没有肉眼,肉眼也解决不了一些很复杂的图路径问题,这时候我们就要借助计算机了,所以写程序就是要用计算机的思维去考虑问题。 迪杰斯特拉算法是一个按路径长度递增的次序产生... -
Dijkstra(迪杰斯特拉算法)的实现-------------------------C,C++,Matlab实现
2018-08-26 16:50:06Dijkstra 算法(中文名:迪杰斯特拉算法)是由荷兰计算机科学家 Edsger Wybe Dijkstra 提出。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说,如果图中的顶点表示城市,而边上的权重表示城市间开车... -
Dijkstra算法入门
2017-03-11 17:06:27Dijkstra 算法是一种解决最短路径问题的经典算法,同时也是计算机科学中最有名的算法之一。其方法简洁,但蕴藏的思想却很深刻。通过学习 Dijkstra 算法,既可以掌握分析、解决问题的方法,也可以作为进一步学习其它... -
图论--最短路径问题--Dijkstra算法和Floyd算法
2017-08-14 14:37:19Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短 路径。 算法具体的形式... -
C++用Dijkstra(迪杰斯特拉)算法求最短路径,秒懂详解!
2019-04-17 14:53:51下面这篇文章就给大家介绍关于C++用Dijkstra算法(迪杰斯特拉算法)求最短路径的方法,下面来一起看看吧。 算法介绍 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是... -
计算机算法(C++语言描述)(第2版)
2015-12-31 10:46:10例如归并排序和快速排序是分治策略的例子,而Kruskal的最小生成树算法和Dijkstra的单源最短路径算法是贪心策略的例子。理解这些策略是掌握设计技能的重要的第一步。 尽管我们深切地认为强调设计以及分析是组织算法... -
挑战408——数据结构(29)——最短路径算法(Dijkstra's Algorithm)
2019-11-20 10:28:49Dijkstra在许多计算领域都具有极大的影响力:编译器,操作系统,并发编程,软件工程,编程语言,算法设计和教学(以及其他!)很难确定哪些领域是他最着名的或者说最厉害的,因为他对CS的影响实在是太大了。 ... -
Warshall算法求传递闭包及Python编程的实现
2021-05-26 01:23:20弗洛伊德算法-Floyd(Floyd-Warshall)-求多源最短路径,求传递闭包Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978... -
银行家算法死锁的避免.doc
2021-08-23 15:34:55实验安排:自选编程语言完成“银行家算法”,记录程序运行结果,完成实验报告。 实验要求:1)设计五个进程{P0,P1,P2,P3,P4}共享三类资源{A,B,C}的系统,{A,B,C}的资源总数量分别为10,5,7。(详见参见课本... -
Python学习从离散实验开始(二) 迪杰斯特拉算法(Dijkstra's Algorithm)
2019-05-17 10:22:57Python学习从离散实验...通过本实验的学习理解Dijkstra算法,并且编码实现最短路径问题。 二、实验内容 Dijkstra算法的理解: 1、 Dijkstra算法一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用O... -
dijkstra算法c语言代码_一文看懂C语言经典八大排序算法,动图加代码!不怕学不会!...
2020-11-21 20:41:32一、前言如果说各种编程语言是程序员的招式,那么数据结构和算法就相当于程序员的内功。想写出精炼、优秀的代码,不通过不断的锤炼,是很难做到的。二、八大排序算法排序算法作为数据结构的重要部分,系统地学习一下... -
最短路径之迪杰斯特拉(Dijkstra)算法
2020-12-22 11:24:51本文主要总结迪杰斯特拉(Dijkstra)算法的原理和算法流程,最后通过程序实现在一个带权值的有向图中,选定某一个起点,求解到达其它节点的最短路径,来加深对算法的理解。1 算法原理迪杰斯特拉(Dijkstra)算法是一个...