Results 1 to 2 of 2

Thread: Programming Challenges

Hybrid View

  1. #1

    Programming Challenges

    Taeshadow thought I should start a new programming challenges thread, so I am.

    Anyway, the first problem is that of finding the shortest path from one node to all other nodes. *Here is my implementation in C++.

    If you are already familiar with the shortest path algorithm, skip to the bottom for the file format.

    I have included some pseudo code for the problem.

    Ok, first off, the following pseudo code is only one implementation of Dijkstra's algorithm (a.k.a. the shortest path first algorithm.) *Look it up on google.

    A few things to realize:
    Quick version: Think of a number of cities on a map and the distances between them. *Dijkstra's algorithm starts at one of the cities and finds the shortest distances to all the other cities on the map from that starting point. *When I describe the algorithm, I will be using the term 'graph' instead of map, and 'node' or 'vertex' instead of cities, as this is a graphing problem (the graph data structure being a data structure that's more generalized than a tree.) *I will also be using the term 'arc' to mean a path between two vertices.

    G is the graph, which also has the sets V (the set of vertices on the graph) and E (which is the set of arcs between the vertices.)

    S is the set of vertices for which we've already found the shortest path to.

    P is an array of vertices and describes the various paths. *Given P[t]=j, j is the vertex just before t in the shortest path to t (if you can't understand it now, hopefully it'll be more clear in the pseudo-code.)

    D is also an array of vertices. *Given D[t]=x, it takes x number of units to go from vertex 1 (the starting vertex) to vertex t.

    C is a matrix (those rectangular thingies with numbers in them, but you do not need to know matrix math or linear algebra to do this problem.) *More specifically, it is a cost matrix. *The number in column t and row j represents the distance (a.k.a. cost, weight) to go from vertex i to j. *The easiest way to think of this is as a two dimensional array. *Column t and row j would then be represented by C[t][j]. *If there is no arc between two points, the distance between them is infinite.

    In my pseudo code, I assume vertices are number from 1 to n, and 1 is the starting point.
    Code:
    shortest(Graph G, matrix C)
     * S={1} // S initially has 1 in it
     * for 1 to n in i do
     * * *P[i]=1
     * * *D[i]=C[1][i]
    
     * for 1 to n-1 in i do
     * * *Let w be D[t] such that D[t]<D[x] for every x in V - S
     * * *S=Union(S, w)
     * * *for each v such that v is adjacent to i do
     * * * * if D[v]>D[w]+C[w][v]
     * * * * * *P[v]=w
     * * * * * *D[v]=D[w]+C[w][v]
    Now that you understand what and how Dijkstra's algorithm works, I need to explain to you what the file format looks like.

    The following is a sample graph file:
    Code:
    7
    1 2 2
    1 3 4
    1 4 7
    2 4 3
    2 5 10
    3 4 2
    4 5 7
    3 6 5
    4 6 8
    4 7 10
    5 7 6
    6 7 1
    The first number is the number of vertices in the graph. *As you can see, each subsequent line has three numbers. *The first two being vertices and the third being the distance to go from the first vertex in that line to the second vertex. *Unless specified elsewhere, this does not work in reverse (i.e. this is a directed graph and i.e. these are like one-way roads.)

    So, take the second line for example (1 2 2). *It takes two units to go from vertex 1 to vertex 2. *Since it is not specified elsewhere, you cannot go from vertex 2 to vertex one.

    Another example. *Let's use the last line (6 7 1). *It takes one unit to go from vertex 6 to vertex 7. *You cannot go from vertex 7 to vertex 6.

    PS Sorry about the indentation in my example. *It somehow got screwed up when I sent it to CCAE.

    PPS Weights are assumed to be positive.

  2. #2

    Re: Programming Challenges

    I might participate on this after this week. I have a killer project due Thursday. This is my last week of college. I'm glad to be graduating.

Similar Threads

  1. Need Help with Network Programming
    By omidkamangar in forum Programming
    Replies: 1
    Last Post: 05-01-2006, 03:23 PM
  2. Microsoft Search Engine Challenges Google
    By genesis in forum Windows - General Topics
    Replies: 10
    Last Post: 02-04-2005, 09:21 PM
  3. Programming
    By imported_n00b in forum Announcements and Suggestions
    Replies: 12
    Last Post: 09-17-2004, 06:35 PM
  4. Programming
    By Asbenson in forum General Chat
    Replies: 34
    Last Post: 06-19-2004, 04:54 AM
  5. Programming challenges
    By ndogg in forum Programming
    Replies: 21
    Last Post: 03-01-2002, 09:49 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •