source: distools/dspath.m @ 122

Last change on this file since 122 was 10, checked in by bduin, 14 years ago
File size: 1.7 KB
RevLine 
[10]1%DSPATH  Single Shortest Path in a (Dissimilarity) Graph
2%
3%   [D,P] = DSPATH (A,i,j)
4%
5% INPUT
6%   A   NxN Weight / dissimilarity matrix or dataset
7%   i,j Vertices for which the shortest path should be found
8%
9% OUTPUT
10%   D   Distance of the shortest path
11%   P   List of edges of the shortest path
12%
13% DESCRIPTION
14% Determines the shortest path between two vertices i and j. The Dijkstra's
15% algorithm is used. Currently, it is not optimized fro speed in Matlab.
16% A is a NxN matrix of weights (or a distance matrix) representing a graph
17% G(V,E). V is a set of vertices, |V| = N, and E is a set of edges. If there
18% is no edge between i and j then A(i,j) = INF. Use DSPATHS(A,'F') if all
19% shortest paths should be computed.
20%
21% SEE ALSO
22% DSPATHS
23%
24% LITERATURE
25% Any book on graph algorithms or basic algorithms in computer science.
26
27% Elzbieta Pekalska, ela.pekalska@googlemail.com
28% Faculty of EWI, Delft University of Technology, The Netherlands and
29% School of Computer Science, University of Manchester
30
31
32function [d, pt] = dspath(A,s,t)
33
34A = +A;
35[n,m] = size(A);
36
37I = (1:n);
38dmin(I)  = 1e10;
39final(I) = 0;
40pred(I)  = -1;
41
42
43I(s)     = [];
44dmin(s)  = 0;
45final(s) = 1;
46last     = s;
47
48while ~final(t)
49  dminnew = dmin(last) + A(last,I);
50  Z = find(dminnew < dmin(I));
51  dmin(I(Z)) = dminnew(Z);
52  pred(I(Z)) = last;
53  [ss,last]  = min(dmin(I));
54  last = I(last);
55  final(last) = 1;
56  I = setdiff(I,last);
57end
58
59if nargout > 1,
60  if pred(t) ~= -1   % there is a path
61    k  = t;
62    pt = t;
63    while k ~= s,
64      pt = [pred(k) pt];
65      k  = pred(k);
66    end
67  else
68    pt = [];
69  end
70end
71
72d = dmin(t);
73return;
Note: See TracBrowser for help on using the repository browser.