Home > matgraph > @graph > find_path.m

find_path

PURPOSE ^

find_path(g,u,v) --- find a shortest path from u to v

SYNOPSIS ^

function p = find_path(g,u,v)

DESCRIPTION ^

 find_path(g,u,v) --- find a shortest path from u to v

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function p = find_path(g,u,v)
0002 % find_path(g,u,v) --- find a shortest path from u to v
0003 
0004 n = nv(g);
0005 
0006 if (u<1) | (u>n) | (v<1) | (v>n)
0007     p = [];
0008     return
0009 end
0010 
0011 if u==v
0012     p = u;
0013     return
0014 end
0015 
0016 q_init(n+1); 
0017 track = zeros(1,n);
0018 track(v) = v;
0019 
0020 q_push(v); 
0021 
0022 while(q_size > 0)
0023     t = q_pop_front;
0024     if t==u
0025         break
0026     end
0027     push_list = neighbors(g,t);
0028     for s = push_list
0029         if (track(s) == 0)
0030             track(s) = t;
0031             q_push(s);
0032         end
0033     end
0034 end
0035 
0036 if track(u) == 0
0037     p = [];
0038     return
0039 end
0040 
0041 p = [];
0042 last = u;
0043 while (last ~= v)
0044     p = [p,last];
0045     last = track(last);
0046 end
0047 p = [p,v];
0048 
0049 
0050 q_init(1);

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003