'k, I read through all the posts, and I'm just sick of coming up with "yet another factoring program." I want to do something more interesting. For example, given a graph, find the shortest path. Let's assume the input for a graph looks like this:

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

Where the first number represents the number of vertices. Let's go to the next line, '1' represents vertex 1 and the first '2' represents vertex 2 and the last '2' represents the weight to go from vertex 1 to vertex 2. The graph is assumed to be directed, so, unless it's specified, you can't go from vertex 2 to vertex 1.

We'll assume that vertices are number from 1 to n, where n is the number of vertices, and all weights are positive. If there is no path between two vertices, then the weight is infinite. The purpose of your program should be to find all the shortest distances from vertex 1 to all other vertices.

Since I'm just interested in the running time for the algorithm that you use, you can use something like the time() function around that part of your algorithm. If the algorithm is too quick for time() (or what ever timing function you use), then try repeating it a large number of times (say, 100000 times.)

I already have a sample implementation of one of the many forms of Dijkstra'

s algorithm in C++ already. To get any interesting timings out of it, though, change MAX to 100000 (this will repeat the algorithm 100000 times).

## Bookmarks