Encontrar la ruta más corta usando el algoritmo de Dijkstra

Question

Necesito encontrar la ruta más corta entre 2 vértices de un gráfico. Tengo una matriz, que contiene todos los pesos. ¿Cómo puedo hacerlo? Actualmente, tengo el siguiente código:

private int[] Dijkstra(int start, int end) 
    { 
     bool[] done = new bool[8]; 
     int[] parent = new int[8]; 
     for (int i = 0; i < parent.Length; i++) 
      parent[i] = -1; 
     int[] distances = new int[8]; 
     for (int i = 0; i < distances.Length; i++) 
      distances[i] = int.MaxValue; 
     distances[start] = 0; 
     int current = start; 
     while (!done[current]) 
     { 
      done[current] = true; 
      for (int i = 0; i < 8; i++) 
      { 
       if (graph[current, i] != int.MaxValue) 
       { 
        int dist = graph[current, i] + distances[current]; 
        if (dist < distances[i]) 
        { 
         distances[i] = dist; 
         parent[i] = current; 
        } 
       } 
      } 
      int min = int.MaxValue; 
      for (int i = 0; i < 8; i++) 
      { 
       if (distances[i] < min&&!done[i]) 
       { 
        current = i; 
        min = distances[i]; 
       } 
      } 
     } 
     return parent; 
    } 

Funciona, pero, sin embargo, no sé cómo hacer que encontrar la ruta más corta entre, por ejemplo, 1 y 3, y el retorno de la ruta como 1 => 4 => 2 => 3.
Gracias de antemano.

Answer 1

Algoritmo de Djikstra utiliza la matriz de los padres a seguir el camino más corto desde el principio hasta el final. Comenzarías en parent [end] y seguirías las entradas de la matriz hasta que hayas vuelto al inicio.

Algunos pseudocódigo:

List<int> shortestPath = new List<int>(); 
int current = end; 
while(current != start) { 
    shortestPath.Add(current); 
    current = parent[current]; 
} 

shortestPath.Reverse(); 

Lo único que se preocupa tiene que preocuparse con su función es la de si o no los valores iniciales y finales aprobadas en son valores apropiados (ya sea o no que en realidad representan vértices en el gráfico , por ejemplo).

Answer 2

pruebe la solución QuickGraph: http://quickgraph.codeplex.com/ (también disponible a través de NuGet)

Answer 3

Una vez que llegue al vértice de destino puede retroceder la ruta al vértice de inicio utilizando la matriz principal. Algo así como (dado que hay una ruta desde el origen al destino):

void backtrack(int source, int dest, vector<int> &path) 
{ 
    path.push_back(dest); 

    for(int vertex = parent[dest]; vertex != source; vertex = parent[vertex]) 
    path.push_back(vertex); 

    path.push_back(source); 
} 

Nota: la ruta será en orden inverso.