Optimization: principles and algorithms, by Michel Bierlaire
run2120.m
Go to the documentation of this file.
1 %> \file
2 %> Runs example 21.20 with the Jarnik-Prim algorithm for minimum spanning tree (Algorithm 21.4 of \cite Bier15-book)
3 %>
4 %> @note Calls \ref jarnikPrim
5 %> @note Calls \ref prepareNetwork
6 %>
7 %> @ingroup Running
8 %> @author Michel Bierlaire
9 %> @date Sun Mar 29 17:47:37 2015
10 %> @ingroup chap21
11 
12 A = [
13  0 1 2 0 0 0 0 ;
14  1 0 3 4 5 0 0 ;
15  2 3 0 6 7 0 0 ;
16  0 4 6 0 8 9 10 ;
17  0 5 7 8 0 11 12 ;
18  0 0 0 9 11 0 13 ;
19  0 0 0 10 12 13 0 ] ;
20 
21 cost = [ 6 ; # (1,2)
22  7 ; # (1,3)
23  2 ; # (2,3)
24  7 ; # (2,4)
25  4 ; # (2,5)
26  5 ; # (3,4)
27  3 ; # (3,5)
28  1 ; # (4,5)
29  5 ; # (4,6)
30  5 ; # (4,7)
31  5 ; # (5,6)
32  5 ; # (5,7)
33  7 # (6,7)
34  ];
35 
36 spanningTree = jarnikPrim(A,cost) ;
37 
38 arcs = prepareNetwork(A) ;
39 
40 for j = spanningTree'
41  printf("(%d,%d)\n",arcs(j,1),arcs(j,2))
42 endfor
43 
function jarnikPrim(in adj, in cost)
Identifies the minimum spanning tree of an undirected network.
function prepareNetwork(in adj)
Identifies the upstream and downstream nodes of each arc.
Copyright 2015-2016 Michel Bierlaire