这里写目录标题
一、算法原理二、MATLAB实现三、参考文献一、算法原理
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
以下图为例，首先介绍Dijstra的原理。
红字为各结点的编号，黑字为各结点之间的距离。
首先定义几个变量：
节点个数nnn；
二维矩阵W(n×n)W(n×n)W(n×n)：距离(权值)矩阵。连通的结点间即为距离，不连通的结点间为正无穷(InfInfInf)，和自己的距离为0；
一维矩阵visit(1×n)visit(1×n)visit(1×n)：访问矩阵。若第iii个节点已找到最短路径，则visit(i)=0visit(i)=0visit(i)=0，否则等于1，对于初始节点，visit=0visit=0visit=0；
距离矩阵d(1×n)d(1×n)d(1×n)：若第iii个节点已找到最短路径，则d(i)d(i)d(i)为这条路径的距离，否则为0，初始节点d=0d=0d=0；
上一节点矩阵path(1×n)path(1×n)path(1×n)：若第iii个节点找到了最短路径，则pathpathpath存放这一条最短路径的前一个节点，通过对每一节点的回溯，可以找到最短路径。根据距离写出以下距离矩阵W=[063infinfinf6025infinf32034infinf53023infinf4205infinfinf350]W=\begin{bmatrix} 0 & 6 & 3 & inf & inf & inf \\ 6 & 0 & 2 & 5 & inf & inf \\ 3 & 2 & 0 & 3 & 4 & inf \\ inf & 5 & 3 & 0 & 2 & 3 \\ inf & inf & 4 & 2 & 0 & 5 \\ inf & inf & inf & 3 & 5 & 0 \\ \end{bmatrix} W=⎣⎢⎢⎢⎢⎢⎢⎡063infinfinf6025infinf32034infinf53023infinf4205infinfinf350⎦⎥⎥⎥⎥⎥⎥⎤确定初始点为v1v_1v1，则visit(1)=0visit(1)=0visit(1)=0;
在图中，结点上，我们将已找到最短路径的点标为它的最短距离，（可以理解为v1v_1v1点已找到最短路径，距离为0），未找到的其余点表为正无穷（即表示不连通）。
在与v1v_1v1连通的点中，即在矩阵WWW的第1行，寻找最小值，最小值所在列即确定的最短路径的节点，此时v3v_3v3最短，visit(3)=0visit(3)=0visit(3)=0，d(3)=3d(3)=3d(3)=3，对于已找到最短路径的v3v_3v3上一节点为v1v_1v1，path(3)=1path(3)=1path(3)=1
接着，在
与v1v_1v1连通的，且未找到最短距离的节点的距离，以及
与v3v_3v3连通的，且未找到最短距离节点的距离+v3v_3v3的最短距离
以上两种中寻找最短距离，最短为v2v_2v2，visit(2)=0visit(2)=0visit(2)=0，d(2)=5d(2)=5d(2)=5，path(2)=3path(2)=3path(2)=3
重复以上步骤，在
与v1v_1v1连通的，且未找到最短距离的节点的距离
与v3v_3v3连通的，且未找到最短距离节点的距离+v3v_3v3的最短距离
与v2v_2v2连通的，且未找到最短距离节点的距离+v2v_2v2的最短距离
以上三种中寻找最短路径，最短为v4v_4v4，visit(4)=1visit(4)=1visit(4)=1，d(4)=6d(4)=6d(4)=6，path(4)=3path(4)=3path(4)=3
我们可以发现，所要寻找的最短路径即为对于已找到最短路径的点（包括初始结点），在与其连通的，未找到最短路径的结点中，将之间距离与圆圈中的距离（即上一结点已找到的最短路径）相加，求得的最小值。 如果有多个相同的最短距离，任取其中一个。 最终最短路径和距离如下图所示。
二、MATLAB实现
dijkstra函数如下：
function [distance, path] = dijkstra(W, st, e)%% dijkstra单源最短路径算法% 输入：W 权值矩阵 st 搜索的起点 e 搜索的终点% 输出：distance 路径距离 path 最短路径n = length(W);% 节点数D = W(st, :);visit = ones(1, n);visit(st) = 0;% 已访问 0；未访问 1parent = zeros(1, n); % 记录每个节点的上一个节点path = [ ];for i = 1:n-1temp = [ ]; % 从起点出发，找最短距离的下一个点，每次不会重复原来的轨迹，设置visit判断节点是否访问for j = 1:nif visit(j)temp = [temp, D(j)];elsetemp = [temp, inf];endend[value, index] = min(temp);visit(index) = 0; % 更新：如果经过index节点，从起点到每个节点的路径长度更小，则更新，记录前驱节点，方便后面回溯循迹for k = 1:nif D(k) > D(index)+W(index, k)D(k) = D(index)+W(index, k);parent(k) = index;endendenddistance = D(e); % 最短距离% 回溯法：从尾部往前寻找搜索路径t = e;while t ~= st && t > 0path =[t, path];p = parent(t);t = p;endpath = [st, path]; % 最短路径
测试用例代码如下：
clear;clc;% 权值表W = [0 6 3 inf inf inf;6 0 2 5 inf inf;3 2 0 3 4 inf;inf 5 3 0 2 3;inf inf 4 2 0 5;inf inf inf 3 5 0];[distance, path] = dijkstra(W, 1, 4)
Command Window中显示的结果为：
distance =6path =134
三、参考文献
[1] 小东和小凤. 最短路径Dijkstra算法原理及Matlab实现. CSDN博客.
[2] 郝搞笑. 详解 Dijkstra算法以及实现. CSDN博客.
