|
|
What's the correct update formula again for A* with Euclidean heuristic? Update dist[w] to be the sum of dist[v] plus the distance from v to w plus the Euclidean distance from w to d minus the Euclidean distance from v to d. See Sedgewick 21.5. See also the program assignment page for an alternative implementation.
What if there are multiple shortest paths? Print out any one you like.
What's a good way to check my answers? Use the client program Distances.java which only prints out the shortest path distances. You can diff the results against the ones produced by our bare-bones solution. Because of roundoff error (e.g., when taking and summing square roots), don't be alarmed if you are off by 0.0000000001 or so. You also can modify the client programs to do this check automatically rather than using diff.
What do you mean by sublinear time? Each shortest path query should take time substantially less than E or V. In particular, you cannot even afford to explicitly re-initialize the V weights or the V entries of the priority queue before each query. Any loop that goes from 1 to V will ruin the sublinearity and be subject to a significant deduction.
Don't the arrays dist[] and pred[] get re-initialized to 0 each time dijkstra(s, t) is called? Yes! Each time you call new, this is what happens. In the bare-bones version this is done each time dijkstra(s, t) is invoked. If you plan to reuse the arrays from one invocation to the next, you must do something else. For example, use a private class instance variable to retain the information from one invocation to the next, and allocate it in the constructor.
How can I profile my code? Use something like java -Xprof Paths usa.txt < usa-50000short.txt.
What should I do if the two vertices are not connected? Print that their distance is "infinity" or print out that they are not connected.
The client ShortestPath.java only processes one query pair. Am I doing anything wrong? No, this client is mean for visualization and you don't want to draw dozens of paths on top of each other. Use Paths.java or Distances.java for testing multiple query pairs. Your algorithm's efficiency will only be apparent when you process lots of query pairs simultaneously.
I can't see the blue dots that are supposed to represent the vertices that the algorithm examines. Sorry, we didn't yet implement this. It won't be very interesting for the bare bones implementation since it explores all the reachable nodes.
How fast should my algorithm be? Significantly faster than the bare bones implementation.
|
|
Input and output. Here are a number of sample input files. Some files contain maps and some contain lists of query points.
Program report. Please submit a program report answering these questions.
|
|
The client ShortestPath peforms a single shortest path query on the given input file using the first pair of integers from standard input. Note that there are two input streams in play: the map comes from the file specified in the command line argument, whereas the queries come from standard input.% javac ShortestPath.java % java ShortestPath usa.txt < usa-1.txt
The program is painfully slow. Your goal is to optimize Dijkstra.java so that you get the same output, but faster.% javac Paths.java % java Paths usa.txt < usa-5000short.txt