# Thread: Should we have a small programming challenge?

1. ## Re: Should we have a small programming challenge?

Muad Dib: I'm coming to you next time I have trouble with my math. Well actually it would be the first time but still.

2. ## Re: Should we have a small programming challenge?

Muad Dib: I'm coming to you next time I have trouble with my math. Well actually it would be the first time but still.
Uhh, sure...

Anyway, I'm looking forward to someone else's solution to this problem. I'm sure someone else has done this problem before. Do you guys want some pseudo code for Dijkstra's algorithm?

3. ## Re: Should we have a small programming challenge?

Since nobody else is going to speak up i will. I would be interested in seeing the psudo code for this.

jcrowe

4. ## Re: Should we have a small programming challenge?

Uhh, sure...

Anyway, I'm looking forward to someone else's solution to this problem. *I'm sure someone else has done this problem before. *Do you guys want some pseudo code for Dijkstra's algorithm?
Huh... what is Dijkstra?

5. ## Re: Should we have a small programming challenge?

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/paths 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]```

#### Posting Permissions

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