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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 14 of 14

Thread: CHALLENGE - find the shortest path

  1. #1
    Member ice's Avatar
    Join Date
    Nov 2010
    Location
    New Zealand
    Posts
    60
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default 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. #3
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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. #4
    Member ice's Avatar
    Join Date
    Nov 2010
    Location
    New Zealand
    Posts
    60
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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. #5
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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. #6
    Member ice's Avatar
    Join Date
    Nov 2010
    Location
    New Zealand
    Posts
    60
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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. #7
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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.
    Last edited by helloworld922; January 7th, 2011 at 01:18 AM.

  8. #8
    Member ice's Avatar
    Join Date
    Nov 2010
    Location
    New Zealand
    Posts
    60
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: CHALLENGE - find the shortest path

    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

  9. #9
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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. #10
    Member ice's Avatar
    Join Date
    Nov 2010
    Location
    New Zealand
    Posts
    60
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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. #11
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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. #12
    Member ice's Avatar
    Join Date
    Nov 2010
    Location
    New Zealand
    Posts
    60
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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. #13
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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. #14
    Member ice's Avatar
    Join Date
    Nov 2010
    Location
    New Zealand
    Posts
    60
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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>();
            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

Similar Threads

  1. Shared library path
    By sateesh.b in forum Java Native Interface
    Replies: 3
    Last Post: May 13th, 2010, 11:12 PM
  2. Replies: 0
    Last Post: May 11th, 2010, 03:37 AM
  3. Program to print current directory path to the console
    By JavaPF in forum Java Programming Tutorials
    Replies: 1
    Last Post: October 9th, 2009, 12:59 PM
  4. how to get full path name from realtive path
    By priyanka3006 in forum File I/O & Other I/O Streams
    Replies: 8
    Last Post: August 10th, 2009, 04:28 AM
  5. [SOLVED] How to a set java class path?
    By captjade in forum Java Theory & Questions
    Replies: 1
    Last Post: March 10th, 2009, 06:40 AM