Question

图论最短路问题的Dijkstra算法与Matlab程序？

请问一下上图中从V1点到V6点最短的Dijkstra算法与Matlab程序怎样编写，最后的结果需显示起点V1到其它各点最短路径的长度，并记载最短路径生成树。请教各位大侠，给予指点！不甚感激！拜托各位有识之士不吝赐教！

Answer 1

这个Dijkstra算法，matlab有自带的graphshortestpath函数，直接调用即可。我将这个算法给写了个更直观的BestRoad函数，你直接调用即可,具体调用格式如下：。

>> BestRoad
请输入各个路径的起始节点
ab=[1,1,1,1,1,2,2,2,2,3,3,3,4,4,5]
请输入各个路径的终止节点
bb=[2,3,4,5,6,3,4,5,6,4,5,6,5,6,6]
请输入各个路径的权值
w=[12,19,28,40,59,13,20,29,41,14,21,30,15,12,15]
请输入起始节点
Begin=1
请输入终止节点
End=6
是否为等权无向图，0=>NO，1=>YES
dir=0
Biograph object with 6 nodes and 15 edges.

d =

    40


p =

     1     4     6

结果d是最优值，p是最优路径。

Answer 2

% Dijkstra's算法：解决加权图G =(V,E,W)中给定顶点之间的最短路径
% 输入：n x n 权重矩阵 G，无边连通时，距离为无穷
% 举例：
% G = [0 50 inf 40 25 10; 50 0 15 20 inf 25; inf 15 0 10 20 inf; 40 20 10 0 10 25;25 inf 20 10 0 55; 10 25 inf 25 55 0];
% [D in1 in2] =dijkstra(G)

function [D index1 index2] = dijkstra( G)

% 参数初始化：
% pb——P标号信息，D——最短路距离
% index1——标号顶点顺序，index2——标号顶点索引
M = max(G(:));
pb(1:length(G)) = 0;
pb(1) = 1;
index1 = 1;
index2 = ones(1,length(G));
D(1:length(G)) = M;
D(1) = 0;
tmp = 1;
% 更新l(v)，同时记录顶点顺序和顶点索引
while sum(pb)<length(G) %重复步骤2，直到满足停止条件
tb = find(pb == 0);
D(tb) = min(D(tb),D(tmp)+G(tmp,tb));
tmpb = find(D(tb) == min(D(tb)));
tmp = tb(tmpb(1));
pb(tmp) = 1;
index1 = [index1,tmp];
index = index1(find(D(index1) == D(tmp)-G(tmp,index1)));
if length(index) >= 2
index = index(1);
end
index2(tmp) = index; % 记录标号索引
end
D;
index1;
index2;