Optimization: principles and algorithms, by Michel Bierlaire
shortestPath.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 23.1: shortest paths. Implementation of algorithm 23.1 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref runShortestPath.m
5 %> @note Calls \ref prepareNetwork
6 %>
7 %> @author Michel Bierlaire
8 %> @date Thu Apr 9 17:20:42 2015
9 %> @ingroup Algorithms
10 %> @ingroup chap23
11
12 %> Calculate the shortest paths from one origin to all nodes
13 %> @param adj adjacency matrix of the network. Each nonzero entry corresponds to an arc. The value of the entry is the ID of the arc.
14 %> @param cost the cost vector.
15 %> @param orig the origin node
16 %> @return lambda the vector of labels
17 %> @return pred the vector of the predecessors in the shortest path
22  lambda = realmax(nnodes,1) ;
23  lambda(orig) = 0 ;
24 % Length of the smallest simple path
25  lengthmin = (nnodes-1) * min(cost) ;
26  pred(1:nnodes,1) = -1 ;
27  listOfNodes = [orig] ;
28  iter = 0 ;
29  while (!isempty(listOfNodes))
30  node = listOfNodes(1) ;
31  printf("%d\t",iter) ;
32  printf("{") ;
33  printf("%d ",listOfNodes) ;
34  printf("}\t%d\t",node) ;
35  for i=1:nnodes
36  if (lambda(i) == realmax)
37  printf("Inf\t") ;
38  else
39  printf("%d\t",lambda(i)) ;
40  endif
41  endfor
42 % printf("%d\t",pred) ;
43  iter += 1;
44  printf("\n") ;
45  listOfNodes(1) = [] ;
47  if (arcij != 0)
48  nodej = arcs(arcij,2) ;
49  if (lambda(nodej) > lambda(node) + cost(arcij))
50  lambda(nodej) = lambda(node) + cost(arcij) ;
51  if (lambda(nodej) < 0 && lambda(nodej) < lengthmin)
52  error("A cycle of negative cost has been detected")
53  endif
54  pred(nodej) = node ;
55  idx = find(listOfNodes == nodej) ;
56  if (length(idx) == 0)
57  listOfNodes(end+1) = nodej ;
58  endif
59  endif
60  endif
61  endfor
62  endwhile
63  printf("%d\t",iter) ;
64  printf(" {}\t\t") ;
65  for i=1:nnodes
66  if (lambda(i) == realmax)
67  printf("Inf\t") ;
68  else
69  printf("%d\t",lambda(i)) ;
70  endif
71  endfor
72 % printf("%d\t",pred) ;
73  printf("\n") ;
74 endfunction
function shortestPath(in adj, in cost, in orig)
Calculate the shortest paths from one origin to all nodes.