Programming Challenges

**ndogg** · 12-12-2001, 01:47 AM

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]&lt;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]&gt;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:

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.