Shortest path from U to V using at most k nodes
Algorithm flawed

Your comment here is wrong:


  In the k'th run the floyd-warshall algorithm gives the shortest path with k edges.


In the k'th run, the algorithm gives the shortest path from each node to each other node using intermediate nodes from 0..k.

As an example, suppose you had 10 vertices and wanted to find the shortest path between vertices 0 and 9, with max nodes = 2.  If the shortest path was 0 -&gt; 8 -&gt; 9, you would need to run 9 iterations for k before you would find that path.  Unfortunately, by that time you would have found paths using more than 2 nodes.

Here is an example input for the above case demonstrating the problem:


1
10 3 3
0 8 1
8 9 1
0 9 999

Output: 999



Corrected algorithm

Your idea about iterating k times was good, but you need to compute the correct thing on each loop.  What you should be computing is the shortest path from node 0 to each other node using k or fewer nodes in the path.  To do this, you can still use the same three loops, but like this:

    unsigned int new_g0[number_of_nodes];
    for (int k=2 ; k &lt; limit_of_nodes ; k++) {
        memcpy(new_g0, g, sizeof(new_g0));
        for (int i=1 ; i &lt; number_of_nodes ; i++) {
            for (int j=1 ; j &lt; number_of_nodes ; j++) {
                if (g[0][i] != MAX &amp;&amp; g[i][j] != MAX &amp;&amp;
                        g[0][i] + g[i][j] &lt; new_g0[j]) {
                    new_g0[j] = g[0][i] + g[i][j];
                }
            }
        }
        memcpy(g, new_g0, sizeof(new_g0));
    }


The new_g0 array is something I added to avoid modifying the matrix when the loop is still computing the current iteration.  If you modified g[0][j] directly, it could influence another computation in the same loop, causing you to find a path with k+1 nodes instead of k nodes.

The k loop starts at 2 because the original matrix already has the lengths of paths with 2 nodes (the start and end nodes).

While this algorithm is now correct, it has the same run time as your original algorithm, \$O(k*n^2)\$, so it doesn't solve your problem of exceeding the time limit.

Other algorithms

If the number of edges is small compared to the number of vertices, you might be better off using a search algorithm such as a depth first search where you 1) limit the depth and 2) keep track of the best distance so far so you can backtrack immediately whenever you exceed the best distance.

Dijkstra's algorithm is good for finding the shortest path between two nodes, but unfortunately, it is not easy to modify it to also have the constraint that there be at most k nodes in the path.