How to return the n best shortest path (dijkstra algorithm)

Question

Hello I have implemented in C Dijkstra's algorithm to find the shortest path, but I need to return the n shortest paths, anyone have an idea how can I do.

My dijkstra function:

int * Dijkstra(graph **g, int totalVertex, int vStart) {
  int i;
  int *distance = (int*) malloc(totalVertex * sizeof (int));
  int *last = (int*) malloc(totalVertex * sizeof (int));
  int *visited = (int*) calloc(totalVertex, sizeof (int));
  int maxDistance, m;
  graph *vertex;

  for (i = 0; i < totalVertex; i++) {
    distance[i] = MAXINT;
    last[i] = -1;
  }

  distance[vOrigem] = 0;

  while (sum(visited, totalVertex) < totalVertex) {

    maxDistance = MAXINT;

      for (i = 0; i < totalVertex; i++) {
        if ((distance[i] < maxDistance) && (visited[i] == 0)) {
          maxDistance = distance[i];
          m = i;
        }
       }

    vertex = g[m];
    while (vertex != NULL) {
      if ((vertex->distance + distance[m]) < (distance[vertex-> destination])) {
        distance[vertex->destination] = vertex->distance + distance[m];
        last[vertex->destination] = m;
      }
    vertex = vertice->next;
    }
  visited[m] = 1;
  }
  free(distance);
  free(visited);
  return last;
}

I need to call eg 2 times this function and it returns, the two shortest paths in the graph.

Thank you.

No is not, i am studding Dijkstra, I am not asking a solution, just some ideas how could I do. — Ruben Gonçalves
Iteratively run Dijstra, removing the vertices of the solution each time. — tbert

MrWuf MrWuf · Accepted Answer · 2012-05-13T02:55:34

Lets start by calling the actual shortest path S and n is the total number of links in S.

This is going to be tough because you could have a ton of permutations of the paths depending on the network configuration and in order to create the next shortest path, you will have to run the algorithm n more times, setting each of the vertices in the shortest path to Visited[m] = 1 for each run in case the next shortest path uses most, but not all of the same vertices from S.

If you really want to only run this for the two shortest paths, then this will be straightforward. If you want to be able to run this to get an arbitrary number of shortest paths, you are exponentially increase your computation time as you go back and set each of the original path links to Visited.

How to return the n best shortest path (dijkstra algorithm)

1 Answers