锐客网

  1. 首页 > 睿知 > it技术 > >

数学建模算法与应用|最短路问题 、迪克斯特拉（Dijkstra）算法、Floyd算法、matlab、python

Python图论matlab

以下链接是语雀原文，观感更好
https://www.yuque.com/chenyujiao-4zrlp/df8osp/ywckpi
迪克斯特拉（Dijkstra）算法

  • 赋权图 G = ( V , E , W ) G=(V,E,W) G=(V,E,W)，求赋权图中指定的两个顶点 u 0 , v 0 u_0,v_0 u0?,v0?间的具有最小权的路，这条路称为 u 0 , v 0 u_0,v_0 u0?,v0?间的最短路，它的权称为 u 0 , v 0 u_0,v_0 u0?,v0?间的距离，记为 d ( u 0 , v 0 ) d(u_0,v_0) d(u0?,v0?)。
  • 迪克斯特拉（Dijkstra）算法基本思想是每一次都走最短的路，可以处理有向图或无向图。
  • 当权为负数时，不能使用Dijkstra算法，要使用Floyd算法。
例子 某公司在6个城市 c 1 , . . . , c 6 c_1,...,c_6 c1?,...,c6?有分公司，下表是两个城市之间的票价，若无直接航班，则为 ∞ \infty ∞。求 c 1 c_1 c1?到其他城市的票价最便宜的路线图。
a = [ 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0 ] a=\left[ \begin{array}{cccccc} 0 & 50 & \infty & 40 & 25 & 10\\ 50 & 0 & 15 & 20 & \infty & 25\\ \infty & 15 & 0 & 10 & 20 & \infty\\ 40 & 20 & 10 & 0 & 10 & 25\\ 25 & \infty & 20 & 10 & 0 & 55\\ 10 & 25 & \infty & 25 & 55 & 0\\ \end{array} \right] a=?????????050∞402510?5001520∞25?∞1501020∞?40201001025?25∞2010055?1025∞25550??????????
演示过程
  • 先理解迪克斯特拉（Dojkstra）算法的思想，故演示如何寻找最短路径
数学建模算法与应用|最短路问题 、迪克斯特拉（Dijkstra）算法、Floyd算法、matlab、python
文章图片

  1. 初始化，visited是是否被标记为最优路径，distance是和初始节点的距离，parent_index是当前节点的父节点
节点(index) 1 2 3 4 5 6
visited 0 0 0 0 0 0
distance inf inf inf inf inf inf
parent_index -1 -1 -1 -1 -1 -1
  1. 从节点1开始，当前节点为1
节点(index) 1 2 3 4 5 6
visited 1 0 0 0 0 0
distance 0 inf inf inf inf inf
parent_index 1 -1 -1 -1 -1 -1
  1. 将（未被访问节点的distance）和（当前节点的distance+当前节点到未被访问节点的距离）比较大小，由于40
节点(index) 1 2 3 4 5 6
visited 1 0 0 0 0 0
distance 0 inf inf 40 25 10
parent_index 1 -1 -1 1 1 1
未被访问节点中节点6的distance最小，所以标记6为已访问，当前节点为6
节点(index) 1 2 3 4 5 6
visited 1 0 0 0 0 1
distance 0 inf inf 40 25 10
parent_index 1 -1 -1 1 1 1
  1. 10+a(6,2)=10+25=35
【数学建模算法与应用|最短路问题 、迪克斯特拉（Dijkstra）算法、Floyd算法、matlab、python】10+a(6,3)=10+inf，不更新节点3
10+a(6,4)=10+25=35<40，更新节点4的distance和parent_index
10+a(6,5)=10+55>25，不更新节点5
节点(index) 1 2 3 4 5 6
visited 1 0 0 0 1 1
distance 0 35 inf 35 25 10
parent_index 1 6 -1 6 1 1
未被访问节点中节点5的distance最小，所以标记5为已访问，当前节点为5
节点(index) 1 2 3 4 5 6
visited 1 0 0 0 1 1
distance 0 35 inf 35 25 10
parent_index 1 6 -1 6 1 1
  1. 25+a(5,2)=25+inf，不更新节点2
25+a(5,3)=25+20=45 25+a(5,4)=25+10=35，不更新节点4
节点(index) 1 2 3 4 5 6
visited 1 0 0 0 1 1
distance 0 35 45 35 25 10
parent_index 1 6 5 6 1 1
未被访问节点中节点2的distance最小，所以标记2为已访问，当前节点为2（2和4一样大，默认序号小的那个）
节点(index) 1 2 3 4 5 6
visited 1 1 0 0 1 1
distance 0 35 45 35 25 10
parent_index 1 5 5 6 1 1
同样的方法得到最终结果：
节点(index) 1 2 3 4 5 6
visited 1 1 1 1 1 1
distance 0 35 45 35 25 10
parent_index 1 5 5 6 1 1
matlab实现Dijkstra算法
clc,clear %% 初始化邻接矩阵 a=zeros(6); %邻接矩阵初始化 a(1,2)=50; a(1,4)=40; a(1,5)=25; a(1,6)=10; a(2,3)=15; a(2,4)=20; a(2,6)=25; a(3,4)=10; a(3,5)=20; a(4,5)=10; a(4,6)=25; a(5,6)=55; a=a+a'; a(a==0)=inf; for i=1:length(a) a(i,i)=0; end %% 确定初始节点，初始化变量 start_index=1; %初始节点 temp=start_index; %当前节点 distance=repelem(inf,length(a)); %初始化所有节点和初始节点的距离 distance(temp)=0; parent_index=repelem(-1,length(a)); %父节点 parent_index(temp)=1; visited=zeros(1,length(a)); %节点是否已经被访问 visited(temp)=1; %节点1被访问%%各节点到初始节点的最短距离 while sum(visited)

python实现Dijkstra算法
a=np.array([[0,50,np.inf,40,25,10],[0,0,15,20,np.inf,25],[0,0,0,10,20,np.inf],[0,0,0,0,10,25],[0,0,0,0,0,55],[0,0,0,0,0,0]]); a=a+a.T a ## 确定初始节点，初始化变量 start_index=0#初始节点 temp=start_index#当前节点 distance=np.array([float('inf')]*len(a))#初始化所有节点和初始节点的距离 distance[temp]=0 parent_index=np.array([-1]*len(a))#父节点 parent_index[temp]=0 visited=np.zeros(len(a))#节点是否已经被访问 visited[temp]=1#节点1被访问 ## 各节点到初始节点的最短距离 while np.sum(visited)

matlab自带最短路径函数
%% matlab自带算法 s = [1 1 1 1 2 2 2 3 3 4 4 5]; t = [2 4 5 6 3 4 6 4 5 5 6 6]; w = [50 40 25 10 15 20 25 10 20 10 25 55]; G = graph(s,t,w); %无向图，digraph有向图 plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) %画出图 set( gca, 'XTick', [], 'YTick', [] ); [P,d] = shortestpath(G, 1, 4); %P是1到4的最短路径，d是最短距离， %无向图且所有边权重均为非负数时默认Dijkstra算法，具体情形可自行查询% 在图中高亮我们的最短路径 myplot = plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2); %首先将图赋给一个变量 highlight(myplot, P, 'EdgeColor', 'r')%对这个变量即我们刚刚绘制的图形进行高亮处理（给边加上r红色）% 求出任意两点的最短路径矩阵 D = distances(G)；% 找出给定范围内的所有点nearest(G,s,d) % 返回图形 G 中与节点 s 的距离在 d 之内的所有节点 [nodeIDs,dist] = nearest(G, 2, 30); >> P P = 154>> d d = 35>> D D = 03545352510 35015203025 45150102035 35201001025 25302010035 10253525350>> nodeIDs nodeIDs = 3 4 6 5>> dist dist = 15 20 25 30

数学建模算法与应用|最短路问题 、迪克斯特拉（Dijkstra）算法、Floyd算法、matlab、python
文章图片

Floyd算法
  • Floyd算法可以得到任意两个顶点之间的最短距离和路径
  • 对于赋权图 G = ( V , E , A 0 ) G=(V,E,A_0) G=(V,E,A0?)，其中顶点集 V = { v 1 , . . . , v n } V=\{v_1,...,v_n\} V={v1?,...,vn?}，邻接矩阵
A 0 = [ a 11 a 12 . . . a 1 n a 21 a 22 . . . a 2 n . . . . . . . . . . . . a n 1 a n 2 . . . a n n ] A_0=\left[ \begin{array}{cccc} a_{11}&a_{12}&...&a_{1n}\\ a_{21}&a_{22}&...&a_{2n}\\ ...&...&...&...\\ a_{n1}&a_{n2}&...&a_{nn}\\ \end{array}\right] A0?=?????a11?a21?...an1??a12?a22?...an2??............?a1n?a2n?...ann???????
a i j = { 权 值 , 当 v i 与 v j 之 间 有 边 时 ∞ , 当 v i 与 v j 之 间 有 边 时 , i =? j a_{ij}= \begin{cases} 权值,&当v_i与v_j之间有边时\\ \infty,&当v_i与v_j之间有边时\\ \end{cases},i\not =j aij?={权值,∞,?当vi?与vj?之间有边时当vi?与vj?之间有边时?,i?=j
a i i = 0 , i = 1 , 2 , . . . , n a_{ii}=0,i=1,2,...,n aii?=0,i=1,2,...,n
  • Floyd算法的基本思想是递推产生一个矩阵序列 A 1 , . . . A k , . . . , A n A_1,...A_k,...,A_n A1?,...Ak?,...,An?， A i j A_{ij} Aij?表示从顶点 v i v_i vi?到顶点 v j v_j vj?的路径上所经过的顶点序号不大于k的最短路径长度。
  • 计算时用迭代公式
A k ( i , j ) = min ? ( A k ? 1 ( i , j ) , A k ? 1 ( i , k ) + A k ? 1 ( k , j ) ) A_k(i,j)=\min(A_{k-1}(i,j),A_{k-1}(i,k)+A_{k-1}(k,j)) Ak?(i,j)=min(Ak?1?(i,j),Ak?1?(i,k)+Ak?1?(k,j))
最后，当 k = n k=n k=n时， A n A_n An?即是各顶点之间的最短通路值。
演示过程 A 0 = [ 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0 ] A_0=\left[ \begin{array}{cccccc} 0 & 50 & \infty & 40 & 25 & 10\\ 50 & 0 & 15 & 20 & \infty & 25\\ \infty & 15 & 0 & 10 & 20 & \infty\\ 40 & 20 & 10 & 0 & 10 & 25\\ 25 & \infty & 20 & 10 & 0 & 55\\ 10 & 25 & \infty & 25 & 55 & 0\\ \end{array} \right] A0?=?????????050∞402510?5001520∞25?∞1501020∞?40201001025?25∞2010055?1025∞25550??????????
A 1 = [ 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 35 10 25 ∞ 25 35 0 ] A_1=\left[ \begin{array}{cccccc} 0 & 50 & \infty & 40 & 25 & 10\\ 50 & 0 & 15 & 20 & \infty & 25\\ \infty & 15 & 0 & 10 & 20 & \infty\\ 40 & 20 & 10 & 0 & 10 & 25\\ 25 & \infty & 20 & 10 & 0 & \color{red}35\\ 10 & 25 & \infty & 25 & \color{red}35 & 0\\ \end{array} \right] A1?=?????????050∞402510?5001520∞25?∞1501020∞?40201001025?25∞2010035?1025∞25350?????????? P 1 = [ ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 1 ? 1 ? 1 ? 1 ? 1 1 ? 1 ] P_1=\left[ \begin{array}{cccccc} -1 & -1 & -1 & -1 & -1 & -1\\ -1 & -1 & -1 & -1 & -1 & -1\\ -1 & -1 & -1 & -1 & -1 & -1\\ -1 & -1 & -1 & -1 & -1 & -1\\ -1 & -1 & -1 & -1 & -1 & \color{red}1\\ -1 & -1 & -1 & -1 & \color{red}1 & -1\\ \end{array} \right] P1?=??????????1?1?1?1?1?1??1?1?1?1?1?1??1?1?1?1?1?1??1?1?1?1?1?1??1?1?1?1?11??1?1?1?11?1??????????
a i 1 + a 1 j < a i j ? a_{i1}+a_{1j}ai1?+a1j?A 2 = [ 0 50 65 40 25 10 50 0 15 20 ∞ 25 65 15 0 10 20 40 40 20 10 0 10 25 25 ∞ 20 10 0 35 10 25 40 25 35 0 ] A_2=\left[ \begin{array}{cccccc} 0 & 50 & \color{red}65 & 40 & 25 & 10\\ 50 & 0 & 15 & 20 & \infty & 25\\ \color{red}65 & 15 & 0 & 10 & 20 & \color{red}40\\ 40 & 20 & 10 & 0 & 10 & 25\\ 25 & \infty & 20 & 10 & 0 & 35\\ 10 & 25 & \color{red}40 & 25 & 35 & 0\\ \end{array} \right] A2?=?????????05065402510?5001520∞25?65150102040?40201001025?25∞2010035?10254025350?????????? P 2 = [ ? 1 ? 1 2 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 2 ? 1 ? 1 ? 1 ? 1 2 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 1 ? 1 ? 1 2 ? 1 1 ? 1 ] P_2=\left[ \begin{array}{cccccc} -1 & -1 & \color{red}2 & -1 & -1 & -1\\ -1 & -1 & -1 & -1 & -1 & -1\\ \color{red}2 & -1 & -1 & -1 & -1 & \color{red}2\\ -1 & -1 & -1 & -1 & -1 & -1\\ -1 & -1 & -1 & -1 & -1 & 1\\ -1 & -1 & \color{red}2 & -1 & 1 & -1\\ \end{array} \right] P2?=??????????1?12?1?1?1??1?1?1?1?1?1?2?1?1?1?12??1?1?1?1?1?1??1?1?1?1?11??1?12?11?1??????????
a i 2 + a 2 j < a i j ? a_{i2}+a_{2j}ai2?+a2j? 同理，得
A 6 = [ 0 35 45 35 25 10 35 0 15 20 30 25 45 15 0 10 20 35 35 20 10 0 10 25 25 30 20 10 0 35 10 25 35 25 35 0 ] A_6=\left[ \begin{array}{cccccc} 0 & 35 & 45 & 35 & 25 & 10\\ 35 & 0 & 15 & 20 & 30 & 25\\ 45 & 15 & 0 & 10 & 20 & 35\\ 35 & 20 & 10 & 0 & 10 & 25\\ 25 & 30 & 20 & 10 & 0 & 35\\ 10 & 25 & 35 & 25 & 35 & 0\\ \end{array} \right] A6?=?????????03545352510?35015203025?45150102035?35201001025?25302010035?10253525350?????????? P 6 = [ ? 1 6 5 5 ? 1 ? 1 6 ? 1 ? 1 ? 1 4 ? 1 5 ? 1 ? 1 ? 1 ? 1 4 5 ? 1 ? 1 ? 1 ? 1 ? 1 ? 1 4 ? 1 ? 1 ? 1 1 ? 1 ? 1 4 ? 1 1 ? 1 ] P_6=\left[ \begin{array}{cccccc} -1 & 6 & 5 & 5 & -1 & -1\\ 6 & -1 & -1 & -1 & 4 & -1\\ 5 & -1 & -1 & -1 & -1 & 4\\ 5& -1 & -1 & -1 & -1 & -1\\ -1 & 4 & -1 & -1 & -1 & 1\\ -1 & -1 & 4 & -1 & 1 & -1\\ \end{array} \right] P6?=??????????1655?1?1?6?1?1?14?1?5?1?1?1?14?5?1?1?1?1?1??14?1?1?11??1?14?11?1??????????
顶点 2 到顶点 5 得最短距离是 A 6 ( 2 , 5 ) = 30 A_6(2,5)=30 A6?(2,5)=30， P 6 ( 2 , 5 ) = 4 P_6(2,5)=4 P6?(2,5)=4，2——4——5
看2，4中间是否还有点，由于 P 6 ( 2 , 4 ) = ? 1 P_6(2,4)=-1 P6?(2,4)=?1，所以没有其他点
看4，5中间是否还有点，由于 P 6 ( 4 , ) = ? 1 P_6(4,)=-1 P6?(4,)=?1，所以没有其他点
所以顶点 2 到顶点 5 得最短路径为：2——4——5
matlab代码
clc,clear %% 初始化邻接矩阵 a=zeros(6); %邻接矩阵初始化 a(1,2)=50; a(1,4)=40; a(1,5)=25; a(1,6)=10; a(2,3)=15; a(2,4)=20; a(2,6)=25; a(3,4)=10; a(3,5)=20; a(4,5)=10; a(4,6)=25; a(5,6)=55; a=a+a'; a(a==0)=inf; for i=1:length(a) a(i,i)=0; end %% 初始化path矩阵 n = size(a,1); dist = a; path = repelem(-1,n,n); %% 下面开始三个循环 for k=1:n% 中间节点k从1- n 循环 for i=1:n% 起始节点i从1- n 循环 for j=1:n% 终点节点j从1-n 循环 if dist(i,j)>dist(i,k)+dist(k,j)% 如果i,j两个节点间的最短距离大于i和k的最短距离+k和j的最短距离 dist(i,j)=dist(i,k)+dist(k,j); % 那么我们就令这两个较短的距离之和取代i,j两点之间的最短距离 path(i,j)=k; % 起点为i，终点为j的两个节点之间的最短路径要经过的节点更新为path(i,k) end end end end%% 找出任意两个顶点间的最短路劲 sb=1; %起点 db=6; %终点 d=dist(sb,db); parent=path(sb,:); parent(parent==-1)=sb; mypath=db; t=db; while t~=sb p=parent(t); mypath=[p,mypath]; t=p; end

该算法由matlab代码写出python代码就很简单了，不再展示

    推荐阅读


    上一篇：数学建模算法与应用|插值方法(一维插值、三次样条插值、二维插值的matlab自带函数，python实现/作图)

    下一篇：机器学习|集成学习、boosting、bagging、Adaboost、GBDT、随机森林