标题: 迪杰斯特拉(Dijkstra)算法 [打印本页] 作者: haige 时间: 2009-5-23 14:23 标题: 迪杰斯特拉(Dijkstra)算法 带权图的最短路径问题的matlab函数代码: C# W+ H; J$ N; D, l( y$ `
function y = shortest_path(i,j)0 ~' b6 C& v0 q+ c: z5 N& K) u
a=load('A.mat');7 B- f3 p1 K2 l6 E+ U0 K
A=a.a;* S; I. e/ P4 h3 T4 D6 ^% p4 _
N = length(A); t/ E% ]- G4 L) U- P G; e& @
S = zeros(1,N); - [/ P9 g. ?" x9 ~# g
S(1) = i; ( K" g# ^- ^2 o6 Y6 @8 j$ T) W
dist = A(i,; 3 ^) ^, C) P* {( K. m; U
flag = 0; $ [/ W# J. F( l; v+ n) ^4 @
count = 1; / J0 B F* R: I7 j! j' y
while (flag~=1) 1 Y2 n1 k4 B9 U, k. |. ]: O [value,position] = min(dist); / S" |& J6 R, R3 N, @3 i5 z dist(i) = inf; ! D& T, q0 v+ q# ^ if (position == j) 9 @- |" m2 u" a. r) o9 L flag = 1; 4 d% K3 F5 a) h2 C3 i else1 J1 U% `0 v" q) o0 T
count = count + 1; 1 L2 s: }# N) j0 ^7 u- V! o S(count) = position; $ U& j' R" |. i; G for o = 1:N1 e1 a/ [) D$ T1 k! u' q3 ~
dist(o) = min(dist(o),dist(position)+A(position,o)); 4 g/ l" v+ U9 |* v T: q* Z4 S: n9 f end7 D3 {4 M. Z: x4 k$ D' w
dist(position) = inf; % point can't back to itself,so weight = inf ; Z8 x) f, {/ `% d; }" m- l- C1 k end ' S3 s! v* ^1 _2 n8 L1 R6 W! }end8 o4 B# V: M8 g$ |( J' f p: M% _4 X
y = value;作者: fantimond 时间: 2009-5-25 15:58
This Algorithm is designed to get one available shortest path vertex at every step.Then when it ends, it gave the shortest path value of every vertex from the source.
; 3 ^) ^, C) P* {( K. m; U