图论模型-Dijkstra
程序员文章站
2023-12-22 23:09:52
...
图论模型-Dijkstra
1. 问题
2. Dijkstra算法简介
Dijkstra算法能求一个顶点到另一顶点最短路径。它是由Dijkstra于1959年提出的。实际它能出始点到其它所有顶点的最短路径。Dijkstra算法是一种标号法:给赋权图的每一个顶点记一个数,称为顶点的标号(临时标号,称T标号,或者固定标号,称为P标号)。T标号表示从始顶点到该标点的最短路长的上界;P标号则是从始顶点到该顶点的最短路长。Dijkstra算法步骤如下:
3. 带权邻接矩阵
3.1 不带方向的
3.2 带方向的
矩阵解释:
第一行第一列:v1到v1距离
第一行第二列:v1到v2距离
………………………………
第二行第一列:v2到v1距离
第二行第二列:v2到v2距离
………………………………
后面以此类推
4. 通用代码:
代码一:
tulun1.m
weight= [0 2 8 1 Inf Inf Inf Inf Inf Inf Inf;
2 0 6 Inf 1 Inf Inf Inf Inf Inf Inf;
8 6 0 7 5 1 2 Inf Inf Inf Inf;
1 Inf 7 0 Inf Inf 9 Inf Inf Inf Inf;
Inf 1 5 Inf 0 3 Inf 2 9 Inf Inf;
Inf Inf 1 Inf 3 0 4 Inf 6 Inf Inf;
Inf Inf 2 9 Inf 4 0 Inf 3 1 Inf;
Inf Inf Inf Inf 2 Inf Inf 0 7 Inf 9;
Inf Inf Inf Inf 9 6 3 7 0 1 2;
Inf Inf Inf Inf Inf Inf 1 Inf 1 0 4;
Inf Inf Inf Inf Inf Inf Inf 9 2 4 0;];
[dis, path]=dijkstra(weight,1, 11)
% 第一个参数:带权邻接矩阵;第二个参数:起始点; 第二个参数: 终止点。
% 这三个参数视情况需要改。
代码二
dijkstra.m
function [min,path]=dijkstra(w,start,terminal)
n=size(w,1); label(start)=0; f(start)=start;
for i=1:n
if i~=start
label(i)=inf;
end, end
s(1)=start; u=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);
5. 结果
dis =
13
% 最短距离
path =
1 2 5 6 3 7 10 9 11