Thread: 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
Adelaide
Melbourne
Sydney
WestSydney
Brisbane
4
OR Adelaide 300 Melbourne
HH Melbourne 850 WestSydney 105 Sydney
M7 WestSydney 1130 Brisbane
BushTrack Adelaide 2448 Brisbane
1
Adelaide Brisbane
0

Output for the Sample Input
Number of roads needed from Adelaide to Brisbane is 1.

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

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

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

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

Thank you for your advice. Ok, will have two classes.

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

Thanks heaps

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

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

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>();
        vertexQueue.add(source);
 
        while (!vertexQueue.isEmpty())
        {
            Vertex u = vertexQueue.poll();
 
            // Visit each edge exiting u
            for (Edge e : u.adjacencies)
            {
                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;
                    vertexQueue.add(v);
                }
            }
        }
    }

Thanks heaps