Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: CHALLENGE - find the shortest path

1. ## CHALLENGE - find the shortest path

Hi guys
I got a CHALLENGE here, below question is From the ACM South Pacific Regional Programming Contest 2009. It is a bit long reading, hope you have some patience. Will anyone be able to tell me pseudo code indicating how to solve it?

The motivation for this problem is a directionally impaired friend, who doesn't care about the shortest or quickest routes -- instead, easier is better. Your task is to read the map information from a database of the entire country and produce the route with the smallest number of roads to use for a trip between an origin city and a destination city. You are guaranteed that there will be a path between origin and destination for any query asked.

Input

The input consists of multiple cases. The input for each case consists of three
sections: the first lists the cities, the second lists the roads, and the third lists the
queries. Each case starts with an integer C (1 <= C <= 200) that represents the
number of cities, followed by C lines each containing the name of a city. There is no white space in a city's name.

The next line consists of an integer R (1 <= R <= 100) that represents the number of roads followed by R lines each describing a road. Each road description has the following form:

<RoadName> <CityA> <AB Distance> <CityB>[ <BC Distance> <CityC>[…]]

There is no white space in a road's name. Roads may pass through any number of cities. The cities appear in the order the road passes through them, and no road passes through the same city more than once. Roads are bidirectional. The
distance (an integer number) it takes to follow a road between each pair of cities is the distance listed between these two names.

The next line consists of an integer Q (1 < Q < 100) that represents the number of queries followed by Q lines each describing a query. Each query description has the following form: <origin> <destination>, where <origin> and <destination> are the names of cities.

A case with C equals zero (0) terminates the input data, and should not be processed.

Output

For each query, the output consists of a single line of the following form:
Number of roads needed from <origin> to <destination> is <number>.
<origin> and <destination> are the names of cities, and <number> is the smallest
number of roads needed for the trip.

Sample Input
5
Melbourne
Sydney
WestSydney
Brisbane
4
HH Melbourne 850 WestSydney 105 Sydney
M7 WestSydney 1130 Brisbane
1
0

Output for the Sample Input

Explanation
The Bush Track connects Adelaide and Brisbane, so it is the only road needed.
Note that if there were only 3 roads (OR, HH and M7), all 3 would need to be used.
The traveller would have to take OR from Adelaide to Melbourne, HH from
Melbourne to WestSydney, then M7 from WestSydney to Brisbane.

Thanks a lot

2. ## Re: CHALLENGE - find the shortest path

Looks like a Shortest Path Problem to me. Can be solved with algorithms such as Dijkstra's Algorithm or the Floyd Warshall Algorithm

3. ## Re: CHALLENGE - find the shortest path

The motivation for this problem is a directionally impaired friend, who doesn't care about the shortest or quickest routes -- instead, easier is better.
That's simple, just run Dijkstra's algorithm using an un-weighted map (every connection is weighted the same).

4. ## Re: CHALLENGE - find the shortest path

ok, I have read class Dijkstra, I think the mehtods getShortestPath() and treeWeight() sounds useful, but I don't know how to use them.
Any chance you could continue to tell me a bit more about how to run Dijkstra's algorithm using an un-weighted map?
Thank you heaps

5. ## Re: CHALLENGE - find the shortest path

If you saw the animation on Wikipedia, just replace all the edge costs with 1 and you'll have an un-weighted map. Their pseudo-code can be used verbatim and all you need to do is pass in the correct map. I'm not sure where you're getting those function names from, their pseudo code consists of one function called Dijkstra. There is one slight change to their code you could make, but it's not necessary if you pass in a graph with the correct edge weights (dist_between(u, v) could be replaced with 1, but it will limit your code to only handling un-weighted maps rather than using the same code for weighted and un-weighted).

6. ## Re: CHALLENGE - find the shortest path

Thank you helloworld!
Dijkstra on Wikipedia gives below Pseudocode, I am surprised you said their pseudo-code can be used verbatim, it still looks far too simple to me. After reading the comments after//..., I still don't understand line 3 and 4, any chance you could explain a bit more?
Also what does line 12 - fi mean?
Do I need to have 3 classes to implement this?

1  function Dijkstra(Graph, source):
2      for each vertex v in Graph:           // Initializations
3          dist[v] := infinity ;              // Unknown distance function from source to v
4          previous[v] := undefined ;         // Previous node in optimal path from source
5      end for ;
6      dist[source] := 0 ;                    // Distance from source to source
7      Q := the set of all nodes in Graph ;
// All nodes in the graph are unoptimized - thus are in Q
8      while Q is not empty:                 // The main loop
9          u := vertex in Q with smallest dist[] ;
10          if dist[u] = infinity:
11              break ;                        // all remaining vertices are inaccessible from source
12          fi ;
13          remove u from Q ;
14          for each neighbor v of u:         // where v has not yet been removed from Q.
15              alt := dist[u] + dist_between(u, v) ;
16              if alt < dist[v]:             // Relax (u,v,a)
17                  dist[v] := alt ;
18                  previous[v] := u ;
19              fi  ;
20          end for ;
21      end while ;
22      return dist[] ;
23  end Dijkstra.

Thank you heaps

7. ## Re: CHALLENGE - find the shortest path

fi is short-hand for "end if" (or a backwards if).

Line 3 sets the shortest distance from any other node to the start node at infinity (the furthest distance away). The reason for this is so any real path (no matter how long) will always be less than infinity. You can replicate this using Double.POSITIVE_INFINITY (or Float.POSITIVE_INFINITY).

Line 4 simply states that you have no idea what the previous node for finding the shortest path is. A null can be substituted in.

Yeah, I said verbatim but I guess what I meant was that the algorithm didn't need to be changed, you only need to translate it into Java code.

Lets see..

I think the easiest way is to have 2 classes: A graph class which contains all the vertices, and the vertices will contain a list of the vertices that vertex is connected to. However, the graph class isn't really necessary, it's merely a wrapper class. If you want, you could have a third class for edges, but I don't see that much a need for this.

8. ## Re: CHALLENGE - find the shortest path

If the cities are a number of vertexs, and put them into an arraylist, but how to show the connections between them?

Thanks heaps

9. ## Re: CHALLENGE - find the shortest path

There are a few different ways to represent graphs (well, there are actually more than two but these are probably the easiest two): via a matrix, or via a jagged list. Without going into too much details I can tell you that for maps where the number of connections/city (paths leaving that city) is much less than the number of cities (which is the case for most real maps) then you'll want to use a jagged list.

So, you would have an ArrayList to hold all the destinations, then inside each destination object it would contain a list of other destinations that you can go to from that destination.

10. ## Re: CHALLENGE - find the shortest path

I found these two mehtods getShortestPath() and treeWeight() provided in Class Dijkstra in below link: http://graphstream.sourceforge.net/javadoc/org/miv/graphstream/algorithm/Dijkstra.html
Any idea what it is? The description of above methods sound quite useful in Shortest Path problem. If you think so too, can they be used in this case?
Thanks heaps again

11. ## Re: CHALLENGE - find the shortest path

It's the exact same Dijkstra's algorithm. I have no idea what the treeWeight method is (I didn't look at the code), but I'm pretty sure that getShortestPath() returns a list of nodes which comprise the shortest path from node A to node B.

Sure it can be useful, but wasn't the original purpose to write your own code which implemented Dijkstra's algorithm? Also, implementing Dijkstra's algorithm is quite simple.

12. ## Re: CHALLENGE - find the shortest path

Hi Helloworld922

Thanks for your advice. ..If I really want to try those "ready-to-use" methods, do I just need to put "import org.graphstream.algorithm.Dijkstra" at the top? like import things from Java SE library?

So I put "import.." at the top, but it says "package org.graphstream.algorithm.Dijkstra does not exist"Any idea how I can use that?

Thanks heaps

13. ## Re: CHALLENGE - find the shortest path

You need to make sure that the compiler has access to the classes. There are several ways to do this depending on how you're compiling your code as well as what they're providing you, such as source only, .class files, or a jar file.

14. ## Need explanation for this line of code

Thank you guys.
I got a piece of sample code here for shortest path, it is working. But I don't understand vertexQueue.remove(v), my understanding is "after executing Vertex u = vertexQueue.poll();, there is nothing in the vertexQueue, so how could v get removed by command vertexQueue.remove(v);?"

Can someone explain this?

public static void computePaths(Vertex source)
{
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();

while (!vertexQueue.isEmpty())
{
Vertex u = vertexQueue.poll();

// Visit each edge exiting u
{
Vertex v = e.target;
//double weight = e.weight;
//double distanceThroughU = weight; (wrong one)
double distanceThroughU = u.minDistance + e.weight;
if (distanceThroughU < v.minDistance)
{
vertexQueue.remove(v);
v.minDistance = distanceThroughU;
v.previous = u;