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.
Bookmarks