dijkstra标记法求解单源最短路

---

---

如只需代码，请移步后文

一、dijkstra算法介绍完整版

1.定义概览

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。

问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

2.算法描述

1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

(1) 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。

(2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。

(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。

(4) 重复步骤(2)和(3)，直到遍历完所有顶点。：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。

二、dijkstra介绍 简述版

三、最短路问题思路

1、要在图中寻找最短路，就好比要吃冰棍，要挑出最好吃的一支以后都吃它，就必须把给出的选择都试一遍，所以，要求解最短路，就必须把所有的路都走一遍。
2、各种算法都是竭尽全力地减少走重复的路、更加高效地走完所有可能的路，这是一种贪心的思想。
当然，面对如已知最短路径长度求解最短路的问题，就需要优先选择遍历可能性大的路径。
3、dijkstra算法为了避免走重复的结点，选择对已遍历的结点进行标记；为求出到达各个顶点最短路，选择对已知的最短路进行迭代。
4、在数据结构上，优先考虑邻接矩阵与可达矩阵对结点与边的权值进行储存，无向图为对称矩阵。

四、matlab.m文件（复制粘贴即可执行）

function [ans] = matlabdijkstra(adj,begin,destination)
%% adj 所有节点构成的一个可达矩阵
%% begin 源节点序列号
%% destination  目的节点序列号
%% ans  源节点到目的节点的路径长度
U=1:length(adj);        %没有求出的最短路径节点的集合
next=ones(length(adj),1)*-1;
U(U==begin)=[];
S=begin;                %已经求出最短路径的节点集合
dis=adj(begin,:);
curdis=0;
lastnodes=ones(1,length(dis));
lastnodes=lastnodes*begin;
while length(S)<length(adj)
    mindis=min(dis(U));
    if mindis==inf
        disp('未完成');
        break
    end
    curdis=curdis+mindis;
    [~,index]=find(dis==mindis,1);
    S=[S,index];
    U(U==index)=[];
    lastpath=lastnodes(index);
    next(index,1)=lastpath;
    if index==destination
        break;
    end
    
    for k=1:length(U)
     if(curdis+adj(index,U(k))<dis(U(k)))
         dis(U(k))=curdis+adj(index,U(k));
         lastnodes(U(k))=index;
     end
    end
end

    ans=0;
   while destination~=begin
      str=[num2str(next(destination)),'到',num2str(destination)];
     disp(str);
      if next(destination)<0
         disp('找不到合适路径');
         break;
     end
     ans=adj(next(destination),destination)+ans;
     destination=next(destination);
   end

测试代码：

a=zeros(6);
a(1,2)=6;a(2,3)=5;
a(3,4)=1;a(4,5)=3;
a(5,6)=2;a(6,1)=1;
a(1,4)=10;a(2,5)=4;
a(3,6)=1;
a=a+a';
a(a==0)=inf;

代码分别复制粘贴到matlab同一目录下生成.m即可运行。

总结

本篇博客参考了大量资料，列出部分以飨读者：

Dijkstra算法及其matlab实现
数据结构–图论
matlab–dijkstra算法描述

欢迎大家指点评论！