Optimization: principles and algorithms, by Michel Bierlaire
dijkstra.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 23.2: Dijkstra. Implementation of algorithm 23.2 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref runDijkstra.m
5 %> @note Calls \ref prepareNetwork
6 %>
7 %> @author Michel Bierlaire
8 %> @date Wed Thu Apr 9 17:22:28 2015
9 %> @ingroup Algorithms
10 %> @ingroup chap23
11 
12 %> Calculate the shortest paths from one origin to all nodes using Dijkstra's algorithm
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 of each arc
15 %> @param orig the origin node
16 %> @param printlevel If different from 0, detailes about the iterations are printed. (Default: 0)
17 %> @return [lambda,pred] lambda is the vector of labels, pred is the vector of the predecessors in the shortest path
18 function [lambda,pred] = dijkstra(adj,cost,orig,printlevel=0)
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  [val, index] = min(lambda(listOfNodes)) ;
31  node = listOfNodes(index) ;
32  if (printlevel != 0)
33  printf("%d\t",iter) ;
34  printf("{") ;
35  printf("%d ",listOfNodes) ;
36  printf("}\t%d\t",node) ;
37  for i=1:nnodes
38  if (lambda(i) == realmax)
39  printf("Inf\t") ;
40  else
41  printf("%d\t",lambda(i)) ;
42  endif
43  endfor
44  printf("\n") ;
45  endif
46  iter += 1;
47  listOfNodes(index) = [] ;
48  for arcij = adj(node,:)
49  if (arcij != 0)
50  nodej = arcs(arcij,2) ;
51  if (lambda(nodej) > lambda(node) + cost(arcij))
52  lambda(nodej) = lambda(node) + cost(arcij) ;
53  if (lambda(nodej) < 0 && lambda(nodej) < lengthmin)
54  error("A cycle of negative cost has been detected")
55  endif
56  pred(nodej) = node ;
57  idx = find(listOfNodes == nodej) ;
58  if (length(idx) == 0)
59  listOfNodes(end+1) = nodej ;
60  endif
61  endif
62  endif
63  endfor
64  endwhile
65  if (printlevel != 0)
66  printf("%d\t",iter) ;
67  printf(" {}\t\t") ;
68  for i=1:nnodes
69  if (lambda(i) == realmax)
70  printf("Inf\t") ;
71  else
72  printf("%d\t",lambda(i)) ;
73  endif
74  endfor
75  printf("\n") ;
76  endif
77 endfunction
78 
function prepareNetwork(in adj)
Identifies the upstream and downstream nodes of each arc.
Copyright 2015-2016 Michel Bierlaire