[Instructions] [Search] [Current] [Changes] [Syllabus] [Handouts] [Outlines] [Labs] [Assignments] [Examples] [Bailey Docs] [SamR Docs] [Tutorial] [API]
Held: Monday, May 4, 1998
G | 3| | 1 4 1 9 A---B---C---D---E | | | | 9| 2| 0| | | | | | +---F---+ | | 6 | +-----------+
/** * Compute the shortest paths from a node to every other node in * the graph. * * pre: The graph is initialized. * pre: The root is in the graph. * pre: The graph is nonempty. * post: An array of distance/prevnode pairs is returned. * post: The underlying graph is unaffected. */ Dictionary shortestPaths(Node root) { Dictionary SP; // The cost/previous pairs Dictionary Est; // Estimated " " Node next; // The next node to add to SP Node neighbor; // Neighbors of next; int distance; // The distance to the current node. int newdist; // Potential new distance to neighbor // Initialze "sets". In a real program, we'd need // to choose a particular implementation of Dictionary. SP = new Dictionary(); Est = new Dictionary(); // Initialize Est. Est.put(root, new Pair(0,null)); Iterator node = allNodesInCurrentGraph(); while (nodes.hasMoreElements()) { next = nodes.nextElement(); if (!next.equals(root)) { Est.add(next, new Pair(MAXPATH+1,null)); } } // for // Remove nodes from Est until it is empty. while(!Est.empty()) { // The next line is not legal Java, but its meaning // should be clear. (next,distance) = smallest(Est); if (distance == MAXPATH+1) { // Whatever you want to do if there is no path to some nodes } Iterator neigborhs = next.neighbors(); while (neighbors.hasMoreElements) { // Get a neighbor neighbor = neighbors.nextElement(); // Compute the distance to that neighbor if we pass // through the current node. newdist = distance + weight(next,neighbor); // If that's better than the best known distance, update // the best known distance if (newdist < Est.get(neighbor).distance) { Est.put(neighbor, new Pair(newdist, next)); } // If we've found a better path } // for each neighbor } // while there are nodes left in Est. // Done return SP: } // shortestPaths
changePriority
method?)
On to Graphs, Concluded
Back to Reachability and Shortest Path Algorithms
Outlines:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
Current position in syllabus
[Instructions] [Search] [Current] [Changes] [Syllabus] [Handouts] [Outlines] [Labs] [Assignments] [Examples] [Bailey Docs] [SamR Docs] [Tutorial] [API]
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
This page may be found at http://www.math.grin.edu/~rebelsky/Courses/CS152/98S/home/rebelsky/public_html/Courses/CS152/98S/Outlines/outline.50.html
Source text last modified Tue Jan 12 11:52:32 1999.
This page generated on Mon Jan 25 09:50:10 1999 by SiteWeaver. Validate this page.
Contact our webmaster at rebelsky@math.grin.edu