Shortest path from U to V using at most k nodes

I'm trying to solve a problem that asks for a shortest path between two cities with at most k nodes.

The first line of input has the number of test cases. On the second line 3 integers are given, which are respectively, the number of nodes, the number of edges and the maximum number of nodes in the shortest path. After that all edges are described with 3 integers representing 2 connected cities and a weight of travel from city 1 to city 2.

For the output just print the shortest path. If there is no shortest path print '-1'

I'm using a $O(k * n ^ 2)$ Floyd-Warshall solution. Is there a better solution? This solution is exceeding the time limit.

#include <stdio.h>
#include <string.h>

#define MAX ((unsigned int) -1)

int main(){
unsigned int number_of_cases;
scanf("%u",&number_of_cases);

for (int i = 0; i < number_of_cases; ++i) {
unsigned int number_of_nodes,number_of_edges,limit_of_nodes;
scanf("%u %u %u",&number_of_nodes,&number_of_edges,&limit_of_nodes);

unsigned int g[number_of_nodes][number_of_nodes];
memset(g, -1, sizeof(g));

for (int j = 0; j < number_of_edges; ++j) {
unsigned int u,v,w;
scanf("%u %u %u",&u,&v,&w);
g[u][v] = w < g[u][v] ? w : g[u][v]; //since there is no negative weight... we can choose the minimum one to the adjacency list and ignore the others.
}

/*
In the k'th run the floyd-warshall algorithm gives the shortest path with k edges.
If i want a shortest path with number of nodes = limit_of_nodes . I just need limit_of_nodes - 1 edges.
*/
--limit_of_nodes;
for (int k=0 ; k < limit_of_nodes ; k++)
for (int i=0 ; i < number_of_nodes ; i++)
for (int j=0 ; j < number_of_nodes ; j++)
if (g[i][k] !=  MAX && g[k][j] != MAX && g[i][k] + g[k][j] < g[i][j])
g[i][j] = g[i][k] + g[k][j];

if(g[0][number_of_nodes-1] == MAX )
puts("-1");
else
printf("%u\n", g[0][number_of_nodes-1]);
}

return 0;
}


Some observations:

1. The number of nodes of a solution can't be less than 2 (since the initial and final nodes are in the solution).
2. There are no negative numbers on the input.
3. There can be more than 1 edge between 2 cities. (Is this relevant ?)

Input sample:

3
5 5 3
0 1 2
0 2 1
1 4 3
2 3 1
3 4 2
3 2 2
0 1 1
1 2 1
3 3 2
0 1 1
1 2 1
0 2 3


Output sample:

5
-1
3


A complete description of the problem is here

Algorithm flawed

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 -> 8 -> 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 < limit_of_nodes ; k++) {
memcpy(new_g0, g, sizeof(new_g0));
for (int i=1 ; i < number_of_nodes ; i++) {
for (int j=1 ; j < number_of_nodes ; j++) {
if (g[0][i] != MAX && g[i][j] != MAX &&
g[0][i] + g[i][j] < 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.

• How would you determine an admissibe heuristic for the cost, which doesn't degenerate A* to djikstra's algorithm? – Deduplicator Oct 23 '15 at 15:49
• @Deduplicator Yes that would seem to be a problem. I'll adjust my answer. – JS1 Oct 23 '15 at 17:06