迪克斯特拉求最短路径_floyd算法求最短路径

以下链接是语雀原文，观感更好
https://www.yuque.com/chenyujiao-4zrlp/df8osp/ywckpi

迪克斯特拉（Dijkstra）算法

• 赋权图$G=(V,E,W)$，求赋权图中指定的两个顶点$u_0,v_0$间的具有最小权的路，这条路称为$u_0,v_0$间的最短路，它的权称为$u_0,v_0$间的距离，记为$d(u_0,v_0)$。
• 迪克斯特拉（Dijkstra）算法基本思想是每一次都走最短的路，可以处理有向图或无向图。
• 当权为负数时，不能使用Dijkstra算法，要使用Floyd算法。

例子

某公司在6个城市$c_1,...,c_6$有分公司，下表是两个城市之间的票价，若无直接航班，则为$\infty$。求$c_1$到其他城市的票价最便宜的路线图。
$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]$

演示过程

• 先理解迪克斯特拉（Dojkstra）算法的思想，故演示如何寻找最短路径

1. 初始化，visited是是否被标记为最优路径，distance是和初始节点的距离，parent_index是当前节点的父节点

3. 从节点1开始，当前节点为1

5. 将（未被访问节点的distance）和（当前节点的distance+当前节点到未被访问节点的距离）比较大小，由于40<inf,25<inf,10<inf，所以更新distance和parent_index

未被访问节点中节点6的distance最小，所以标记6为已访问，当前节点为6

3. 10+a(6,2)=10+25=35<inf，更新节点2的distance和parent_index

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

未被访问节点中节点5的distance最小，所以标记5为已访问，当前节点为5

4. 25+a(5,2)=25+inf，不更新节点2

25+a(5,3)=25+20=45<inf，更新节点3的distance和parent_index
25+a(5,4)=25+10=35，不更新节点4

未被访问节点中节点2的distance最小，所以标记2为已访问，当前节点为2（2和4一样大，默认序号小的那个）

同样的方法得到最终结果：

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)<length(a)%节点没有被访问完
    unvisited=find(visited==0);%将还没有被访问的节点索引放进unvisited
    for i=unvisited
        if distance(temp)+a(temp,i)<distance(i)
            distance(i)=distance(temp)+a(temp,i);
            parent_index(i)=temp;
        end
    end
    
    [min_distance,index]=min(distance(unvisited));%找到未被访问的节点和当前节点的最近距离和节点
    temp=unvisited(index);%最小距离对应的下一个节点是unvisited中第index个值
    visited(temp)=1;
end
disp(["各节点为" num2str([1:1:length(a)])]);
disp(["各节点的父节点为" num2str(parent_index)]);
disp(["各节点和初始节点的最短距离" num2str(distance)]);

%%各节点到初始节点的最短路径
for i=1:length(a)
    end_index=i;
    path=[end_index];
    while end_index ~= start_index && parent_index(end_index)~=-1
        path=[path,parent_index(end_index)];
        end_index=parent_index(end_index);
    end
    if parent_index(end_index)==-1
        disp([num2str(i) "无法到达初始节点"]);
    else
        disp([num2str(i) "到初始节点的最短路径" num2str(fliplr(path))]);%fliplr反转
    end
end

    "各节点为"    "1  2  3  4  5  6"

    "各节点的父节点为"    "1  6  5  6  1  1"

    "各节点和初始节点的最短距离"    "0  35  45  35  25  10"

    "1"    "到初始节点的最短路径"    "1"

    "2"    "到初始节点的最短路径"    "1  6  2"

    "3"    "到初始节点的最短路径"    "1  5  3"

    "4"    "到初始节点的最短路径"    "1  6  4"

    "5"    "到初始节点的最短路径"    "1  5"

    "6"    "到初始节点的最短路径"    "1  6"

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)<len(a):#节点没有被访问完
    unvisited=np.where(visited==0)[0]#将还没有被访问的节点索引放进unvisited
    for i in unvisited:
        if distance[temp]+a[temp,i]<distance[i]:
            distance[i]=distance[temp]+a[temp,i]
            parent_index[i]=temp
    min_distance=min(distance[unvisited])
    index=np.where(distance[unvisited]==min_distance)[0][0] #第一个0是因为where得到的是一个元组，要把数组从元组里拿出来，
                                                            #第二个0是当有多个索引时选择第一个
    temp=unvisited[index]#最小距离对应的下一个节点是unvisited中第index个值
    visited[temp]=1

## 初始节点到某个节点的最短路径
parent_index=list(parent_index)#转换成列表可以使用append方法，比较方便
end_index=2
path=[end_index]
while end_index != start_index and parent_index[end_index]!=-1:
    path.append(parent_index[end_index])
    end_index=parent_index[end_index]
if parent_index[end_index]==-1:
    print("初始节点%d无法到达节点%d"%(start_index,end_index))
else:
    print("初始节点%d无法到达节点%d的最短路径为："%(start_index,end_index))
    print(path[::-1])#path倒序输出

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 =
     1     5     4

>> d
d =
    35
    
>> D 
D =
     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
    
>> nodeIDs
nodeIDs =
     3
     4
     6
     5

>> dist
dist =
    15
    20
    25
    30

Floyd算法

• Floyd算法可以得到任意两个顶点之间的最短距离和路径
• 对于赋权图$G=(V,E,A_0)$，其中顶点集 V = { v 1 , . . . , v n } V=\{v_1,…,v_n\} V={
  v1​,...,vn​}，邻接矩阵

$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]$

$a_{ij}=\{\begin{array}{ll}权值,& 当v_i与v_j之间有边时\\ \infty ,& 当v_i与v_j之间有边时\end{array},i\ne j$

$a_{ii}=0,i=1,2,...,n$

• Floyd算法的基本思想是递推产生一个矩阵序列$A_1,...A_k,...,A_n$，$A_{ij}$表示从顶点$v_i$到顶点$v_j$的路径上所经过的顶点序号不大于k的最短路径长度。
• 计算时用迭代公式

$A_k(i,j)=\min (A_{k-1}(i,j),A_{k-1}(i,k)+A_{k-1}(k,j))$
最后，当$k=n$时，$A_n$即是各顶点之间的最短通路值。

演示过程

$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]$

$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& 35\\ 10& 25& \infty & 25& 35& 0\end{array}\right]$$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& 1\\ -1& -1& -1& -1& 1& -1\end{array}\right]$
$a_{i1}+a_{1j}<a_{ij}?$
$A_2=\left[\begin{array}{cccccc}0& 50& 65& 40& 25& 10\\ 50& 0& 15& 20& \infty & 25\\ 65& 15& 0& 10& 20& 40\\ 40& 20& 10& 0& 10& 25\\ 25& \infty & 20& 10& 0& 35\\ 10& 25& 40& 25& 35& 0\end{array}\right]$$P_2=\left[\begin{array}{cccccc}-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\end{array}\right]$
$a_{i2}+a_{2j}<a_{ij}?$
同理，得
$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]$$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]$
顶点 2 到顶点 5 得最短距离是$A_6(2,5)=30$，$P_6(2,5)=4$，2——4——5
看2，4中间是否还有点，由于$P_6(2,4)=-1$，所以没有其他点
看4，5中间是否还有点，由于$P_6(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代码就很简单了，不再展示

今天的文章迪克斯特拉求最短路径_floyd算法求最短路径分享到此就结束了，感谢您的阅读。