用matlab最短路

用graphshortestpath（）函数，可以解决最短路径问题。实现代码如下：

W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21]

DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W)

h = view(biograph(DG,[],'ShowWeights','on'))

[dist,path,pred] = graphshortestpath(DG,1,6)

给出定点x0到u的最短距离在网络图之中，程序如下：clc

clear

%问题：对于无向图实现最短距离

%初始值

%Diikstra算法应用到网络中的最短距离

%求解出父亲点、最短路轻

%创建时间：2020.10.18

w=10111inf infinf inf；%创建邻接矩阵

10 inf 11inf inf inf

Tinf 0 1 inf inf Tinf:

1110111inf

inf 1inf 10 1inf 1:

inf inf inf 110 11

inf inf 11inf 101:

inf inf inf inf 11101

n=size(w.1)

w1=w(1:):

fori=tn

（i)=wT()%贼初值]

(v),Ku0)=0,Ku1)=2,Ku2)=1,Ku3)=8.1(u4)=in

f….

z（)=1%这里所求的z（i)-1就是父亲点的意思

end

s-[1

s(1)=1%1代表U0

u=5(1%这里对于我们的u的初始值选取

K=1

%进行循环更新Kv)、z(v)

whilekcn%此处相当于让其初始值不变往下走

%更新(v)、z(v]

fori=tn

for j=Tk

if i"=s(j)

if 1Dak)+wu.i

Ki)=ku)+w(u,D)

zG)=u

end

end

end

end

%第n次更新

11=1%将更新后的|赋值给1目

for i=tn

for j=Tk

ifi”=s（j)%点集出列，不能选择

K）=lKi)；%边权不改变

elee

)=inf；%无关联的情况下当前点与具余点的

边权为元穷

end

end

end

lv=inf；%边权赋予给无穷

fori=1n %循环vO到v7寻找vO到v7的最短路

ifj)ly%如果边权点小于无穷，则lv返回i）

的值

lv=Ik)

V=i%顶点集更新，并且赋予给

end

end

lv；%输出边权

v%输出顶点集

s(k+1)=v；%出列点

k=k+1

u=s(k)

end

――

Z

输出结果：

1=

01112223

Z=

11112435

其中代表的是最短路径距离，z表示的是最短路径走向。从上述结果可知，路径为，v1--v2-v5-v8其最短距离为1+2+3=6；所以得知该网络图的最短路距离径为6。对于Dijkstra算法得理解父亲点与距离权重，这是理解算法原理的基础！此代码的好处在于，你根据自己的问题，相应的把邻接矩阵改了就可以用！

用这个程序：m文件

function [min,path]=dijkstra(w,start,terminal)

n=size(w,1)label(start)=0f(start)=start

for i=1:n

if i~=start

label(i)=inf

end, end

s(1)=startu=start

while length(s)<n

for i=1:n

ins=0

for j=1:length(s)

if i==s(j)

ins=1

end, end

if ins==0

v=i

if label(v)>(label(u)+w(u,v))

label(v)=(label(u)+w(u,v))f(v)=u

end, end, end

v1=0

k=inf

for i=1:n

ins=0

for j=1:length(s)

if i==s(j)

ins=1

end, end

if ins==0

v=i

if k>label(v)

k=label(v) v1=v

end, end, end

s(length(s)+1)=v1

u=v1

end

min=label(terminal)path(1)=terminal

i=1

while path(i)~=start

path(i+1)=f(path(i))

i=i+1

end

path(i)=start

L=length(path)

path=path(L:-1:1)

调用形式为：

[min,path]=dijkstra(w,start,terminal)

w为邻接矩阵，start为出发点，teminal为终点。

希望帮到你

---