2 %> Run to illustrate the shortest path algorithm (Table 23.2)
8 %> @author Michel Bierlaire
9 %> @date Thu Apr 9 17:20:47 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] = shortestPath(adj,cost,orig) ; 35 printf("List of predecessors in the shortest path tree:\n") ; 39 printf("%d -> %d\n",pred(i),i) function shortestPath(in adj, in cost, in orig)
Calculate the shortest paths from one origin to all nodes.