1 /*
2 *
3 * Copyright (c) 2003 The Regents of the University of California. All
4 * rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * - Neither the name of the University nor the names of its
14 * contributors may be used to endorse or promote products derived
15 * from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
19 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
20 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
24 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
25 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 */
30
31
32 #include <stdlib.h>
33 #include <stdio.h>
34 #include <assert.h>
35 #include <math.h>
36 #include <string.h>
37
38 #include <sys/types.h>
39 #include <netinet/in.h>
40
41 #include "heap.h"
42 #include "dijkstra.h"
43
44
45 /* It seems that had we operated on neighbor-lists, not on adjacency matrices,
46 * we could've done things a bit more efficiently. It does not matter all that
47 * much though */
48
49 /* NOTE. typically, we'd keep all nodes that we haven't finalized yet in the
50 * heap. however, we have to keep "weights" array anyway (since to change
51 * the value corresponding to some key in the heap we need to know current
52 * value). Therefore, we dont add a node to the heap until we relax an
53 * edge leading to this node for the first time (ie. if node's weight is
54 * INIFINITY, it won't be in the heap. However, as soon as we change the
55 * value of the path from inifinity to something else, we enter the node
56 * into the heap) */
57 int
58 dijkstra(ulong **adj, uint num_nodes, uint start, ulong *p)
59 {
60 /* heap used to keep track of the "frontier" */
61 struct heap *h = NULL;
62 /* index of the node we're currently processing (ie finding this node's
63 * neighbors, and determining which one should be picked as the next node to
64 * be processed */
65 ulong cur = start;
66 /* weight of the path from starting node to the current node */
67 ulong cur_weight = 0;
68 /* temp */
69 ulong i;
70 /* current weights (distances from starting node) of the nodes */
71 ulong *weights;
72
73 /* heap which we'll use to keep nodes which are not "finalized" yet */
74 h = heap_alloc();
75
76 /* allocate array which holds weights of paths from starting node */
77 weights = malloc(num_nodes * sizeof(ulong));
78
79 assert(h);
80 assert(adj);
81 assert(p);
82 assert(start < num_nodes);
83 assert(weights);
84
85 /* initialize all weights to "unknown" */
86 for (i = 0; i < num_nodes; i++)
87 {
88 weights[i] = INFINITY;
89 }
90 /* however, "starting node" should have a weight of 0, since its the
91 * distance from itself */
92 weights[start] = 0;
93 /* starting node is it's own predecessor */
94 p[start] = 0;
95
96 /* insert the starting node into the heap */
97 heap_insert(h, start, VAL(0));
98
99 /* heap_peek_max will return negative when it is empty
100 * (it picks the next "current" node. This node represents a node with the
101 * smallest path weight (path from the starting node to this node). See
102 * comment on definition of VAL() for why we use the "max" routines to
103 * extract) */
104 while (0 < heap_extract_max(h, &cur, &cur_weight))
105 {
106 /* ok, lets relax all edges leaving the newly-extracted vertex */
107 cur_weight = VAL(cur_weight);
108 for (i = 0; i < num_nodes; i++)
109 {
110 /* if weight of the path through this node to node 'i' is smaller
111 * then our previous idea of the weight of path to node 'i', we
112 * opt to use this path */
113 if ( (i != cur) /* dont check path to self */
114 && (adj[cur][i] != INFINITY) /* path exists */
115 && (cur_weight + adj[cur][i] < weights[i])) /* path shorter */
116 {
117 /* if weight of the node 'i' is infinity, the node has not been
118 * added to the heap yet */
119 if (weights[i] == INFINITY)
120 {
121 heap_insert(h, i, VAL(cur_weight + adj[cur][i]));
122 }
123 else
124 {
125 int ret = 0;
126 /* ah, so the node is already in the heap. */
127 ret = heap_change_key_value(h, i, VAL(weights[i]),
128 VAL(cur_weight + adj[cur][i]));
129 /* Changing the value only fails if we can't find the node,
130 * but that should never really happen */
131 assert(ret > 0);
132 }
133
134 weights[i] = cur_weight + adj[cur][i];
135
136 /* mark this node as a predecessor of the node 'i', since the
137 * path now goes through "us" */
138 p[i] = cur;
139 }
140 }
141 }
142
143 free(weights);
144 heap_destroy(h);
145
146 return 0;
147 }
148
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.