2 %> Run to illustrate Dijkstra
's algortihm (Table 23.4) 4 %> @note Calls \ref dijkstra 8 %> @author Michel Bierlaire 9 %> @date Thu Apr 9 17:26:53 2015 11 # Arc 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 12 cost = [ 8 1 1 1 1 8 1 1 8 8 8 1 8 1 1 8 8 8 1 1 1 8 8 8]' ;
14 adj = [ 0 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 ;
15 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 ;
16 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 ;
17 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 ;
18 0 0 0 0 0 6 0 0 7 0 0 0 0 0 0 0 ;
19 0 8 0 0 0 0 9 0 0 0 0 0 0 0 0 0 ;
20 0 0 10 0 0 0 0 11 0 0 0 0 0 0 0 0 ;
21 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 ;
22 0 0 0 0 0 0 0 0 0 13 0 0 14 0 0 0 ;
23 0 0 0 0 0 15 0 0 0 0 16 0 0 0 0 0 ;
24 0 0 0 0 0 0 17 0 0 0 0 18 0 0 0 0 ;
25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 ;
26 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 0 ;
27 0 0 0 0 0 0 0 0 0 21 0 0 0 0 22 0 ;
28 0 0 0 0 0 0 0 0 0 0 23 0 0 0 0 24 ;
29 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ];
33 [lambda,pred] =
dijkstra(adj,cost,orig,printlevel) ;
35 printf(
"List of predecessors in the shortest path tree:\n") ;
39 printf(
"%d -> %d\n",pred(i),i)
function dijkstra(in adj, in cost, in orig, in printlevel)
Calculate the shortest paths from one origin to all nodes using Dijkstra's algorithm.