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
18 function [lambda,pred] = shortestPath(adj,cost,orig)
19  addpath("../chap21") ;
20  arcs = prepareNetwork(adj) ;
21  nnodes = rows(adj) ;
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) = [] ;
46  for arcij = adj(node,:)
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.
function prepareNetwork(in adj)
Identifies the upstream and downstream nodes of each arc.
Copyright 2015-2016 Michel Bierlaire