Optimization: principles and algorithms, by Michel Bierlaire
runDijkstra.m
Go to the documentation of this file.
1 %> \file
2 %> Run to illustrate Dijkstra's algortihm (Table 23.4)
3 %>
4 %> @note Calls \ref dijkstra
5 %>
6 %> @ingroup chap23
7 %> @ingroup Running
8 %> @author Michel Bierlaire
9 %> @date Thu Apr 9 17:26:53 2015
10 
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]' ;
13 
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 ];
30 
31 orig = 1 ;
32 printlevel = 1 ;
33 [lambda,pred] = dijkstra(adj,cost,orig,printlevel) ;
34 
35 printf("List of predecessors in the shortest path tree:\n") ;
36 nnodes = rows(adj) ;
37 for i=1:nnodes
38  if (pred(i) != -1)
39  printf("%d -> %d\n",pred(i),i)
40  endif
41 endfor
function dijkstra(in adj, in cost, in orig, in printlevel)
Calculate the shortest paths from one origin to all nodes using Dijkstra's algorithm.
Copyright 2015-2016 Michel Bierlaire