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.

Now that you understand what and how Dijkstra's algorithm works, I need to explain to you what the file format looks like.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]

The following is a sample graph file:

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

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