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 /* Implementation of dijkstra algorithm, which uses priority queues (implemented
33 * as a binary heap) */
34
35 #ifndef DIJKSTRA_H_
36 #define DIJKSTRA_H_
37
38 #define INFINITY ULONG_MAX
39 /* because heap was originally designed to operate in terms of "max" (in order
40 * to avoid making a new "min" version, we simply store complements of the
41 * weights */
42 #define VAL(V) (INFINITY - (V))
43
44 /*
45 * NOTE:
46 * 'adj' array is used to store some intermediate information, so that it
47 * is pretty much guaranteed to contain information other then the one
48 * supplied to it at the time the function is called. If this is not
49 * desirable, make a copy.
50 *
51 * input:
52 * adj - adjacency matrix (element adj[i][j] has a cost of edge
53 * 'i'-'j',
54 * (ULONG_MAX is used as some special sentinel value, so that
55 * value is illegal as a cost of an edge)
56 * num_nodes - number of nodes
57 * start - index of the starting node
58 *
59 * output:
60 * p - predecessor array (must be pre-allocated and have
61 * 'num_nodes' elements). After completion, every element p[i]
62 * will contain index of a node which would be the last node
63 * visited before node 'i', along the path from node 'start' to
64 * node 'i'
65 *
66 * returns:
67 *
68 *
69 */
70 int dijkstra(ulong **adj, uint num_nodes, uint start, ulong *p);
71
72
73 #endif /* DIJKSTRA_H_ */
74
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.