Implementación del algoritmo de Dijkstra

Question

Me han encargado (coursework @ university) implementar una forma de búsqueda de ruta. Ahora, dentro de las especificaciones, podría implementar una fuerza bruta, ya que hay un límite en la cantidad de nodos para buscar (comenzar, dos en el medio, el final), pero quiero reutilizar este código y vine a implementar Dijkstra's algorithm .

He visto el pseudo en Wikipedia y un amigo también escribió algo para mí, pero a toda máquina no tiene sentido. El algoritmo parece bastante simple y no es un problema para mí entenderlo, pero simplemente no puedo visualizar el código que se daría cuenta de eso.

¿Alguna sugerencia/sugerencia?

Editar para algunas confusiones:
Sí, hay un nodo de destino y un nodo de origen.
Estoy buscando implementar Dijkstra en un caso general, no en el caso de "solo dos paradas intermedias", porque deseo usar el código nuevamente después. De lo contrario, escribiría una implementación de fuerza bruta.
El problema específico con el que estoy teniendo problemas es almacenar las rutas sub-óptimas a medio formar, en caso de que puedan ser óptimas. Cuando visito un nodo dado, simplemente no veo cómo voy a actualizar todas las conexiones que lo atraviesan.
Más edición:
Pasando por un par de respuestas ahora y probando.

REALMENTE EDIT: Olvidé mencionar una complicación seria, que es que dos vértices pueden tener hasta UINT_MAX diferentes distancias entre ellos. Lo siento. De hecho, el hecho de que olvidé lidiar con esto es probablemente la causa del maldito problema, en primer lugar, aunque la solución: elegir la más corta es afortunadamente obvio para mí. No es de extrañar que el pseudo de otra persona para una variable de distancia no tuviera en cuenta mi distancia variable.

Answer 1

He aquí un desglose de alto nivel del algoritmo de Dijkstra:

que se adhieren todos los vértices en una cola de prioridad donde todos los vértices tienen una prioridad (distancia) del infinito excepto por el vértice fuente, que tiene una distancia de cero (el vértice fuente está a cero unidades de distancia de sí mismo, ¿verdad?).

Aparece la cola de prioridad. El vértice eliminado es el vértice con la distancia más corta desde la fuente. Obviamente, el primer vértice extraído de la cola es la fuente. Bueno, llama al vértice que apareció v.

Mire cada uno de los vecinos de v. Todos ellos tendrán una distancia mayor que v (de lo contrario, ya los hubiéramos sacado de la cola, ¿no?). Digamos que v tiene una distancia de 3, y v tiene 3 vecinos x (dist-de-fuente: 5), y (dist-de-fuente: 10) y z (dist- from-source: infinito).

Ahora miramos la distancia de cada vecino de v. Digamos que son: x - 3, y - 2, z - 4. Esto significa que el camino de la fuente al x que pasa por v tiene una distancia de | v | + 3 (3 + 3 = 6), y tiene una distancia de 5 (3 + 2 = 5) yz tiene una distancia de 7 (3 + 4 = 7).

El camino a través de xv es más largo que el actual camino más corto a x por lo que ignoran. Sin embargo, las rutas a y y z que pasan por v son más cortas que la ruta más corta conocida anterior, por lo que las actualizamos.

Sigues haciendo esto hasta que hayas pasado por todos los vértices. En cada punto, cuando saca el min de la cola de prioridad, sabe que ha encontrado la ruta más corta hacia ese vértice, porque cualquier posible ruta más corta debe pasar por un vértice con una distancia inferior a v, lo que significa que tendríamos ya apareció eso de la cola.

Answer 2

El Wikipedia article link que metí en el OP ofrece una descripción muy clara y concisa, junto con gráficos animados.

La clave que puede faltar (?) Es que en cada paso del algoritmo posiblemente estará actualizando la ruta más corta a cada nodo conectado a su nodo "actual". Para su caso de "diamante" de cuatro nodos, si A es el inicio y D es el final, primero calcula las distancias a B y C, luego desde B calcula la distancia de A a D y luego lo hace a través de C. Si el camino a través de C es más corto, entonces el "camino más corto de A a D" pasa por C. Si el camino por C es más largo, entonces el camino más corto pasa por B. Esto obviamente (?) se extenderá a redes más complejas.

En de la OP Realmente Edición: no importa cuántas conexiones que tiene entre dos nodos. De hecho, ese es el punto del algoritmo, verifique todas las conexiones a través de todas las rutas posibles. Si el nodo A y el nodo B están conectados por dos carreteras, y desea el camino más corto, no se preocupe por el camino más largo, simplemente deséchelo. Siempre trate de descartar datos que sepa que no son relevantes para su problema.

Answer 3

Lo primero que necesita es una forma de representar un gráfico. Normalmente, esta es una colección de objetos vertex, cada uno de los cuales contiene una lista de adyacencia. En C++ esto podría ser una lista de punteros a otros vértices. Asegúrate de que los vértices sean LessThanComparable. Podría, por ejemplo, dar a cada uno un número de identificación único.

Luego, el código en Wikipedia debería tener más sentido. Cada vez que tenga un pseudocódigo como dist[v], desea usar un map<VertexIdNumber, double>.

Answer 4

Implementar el algoritmo de Dijksta en C++ si nunca has escrito algo así es un problema bastante intenso. Después de leer la página de Wikipedia, aquí hay algunas ideas para comenzar.

struct Vertex { 
    int id; 
    std::vector<int> neighbors; 
    int dist_from_source; // need some sentry value for "infinity" 
    int prev; // need some sentry value for "undefined" 
}; 

Esto se basa en las primeras líneas de pseudocódigo. Un Graph podría ser std::vector<Vertex> junto con alguna forma de identificar la distancia entre dos vértices.

8  u := vertex in Q with smallest dist[] 

Esta línea indica una necesidad de std::make_heap (no priority_queue como veremos más adelante). Haga un vector separado para esto porque necesitaremos agregar y eliminar cosas de él.Busque cómo proporcionar un predicado que coloque el vértice con el dist_from_source más bajo en la parte superior del montón.

12  for each neighbor v of u: // where v has not yet been removed from Q. 

He aquí por qué no usamos priority_queue para Q. Debe averiguar si v aún se encuentra en Q. Una prioridad_cola no te deja hacer eso.

13  alt := dist[u] + dist_between(u, v) 

Ahora necesita la función de distancia que viene con Graph. No dijiste cómo se definen los datos del gráfico, por lo que estás un poco solo aquí.

17  return dist[] 

Esta línea solo significa devolver los datos que sean necesarios para generar las rutas más cortas. Es básicamente el conjunto de vértices con todos ellos tener prev y dist_from_source rellenado.

Answer 5

La cuestión específica que estoy teniendo un pequeño problema con está almacenando los caminos a medio formar sub-óptimo, en caso de que pueda ser óptimo Cuando visito un nodo dado, simplemente no veo cómo voy a actualizar todas las conexiones que lo atraviesan.

Creo que tal vez esté malinterpretando un poco el algoritmo. Dijkstra funciona explorando los nodos en orden creciente de distancia; por lo que está garantizado que ha encontrado la distancia mínima y la ruta óptima a cualquier nodo que haya sido etiquetado permanentemente.

normalmente no se almacene cualquier ruta explícita cuando se ejecuta el algoritmo. En cambio, considere que está construyendo un árbol de expansión en el gráfico, por lo que solo hay una forma de llegar a cada nodo en ese árbol. Todo lo que necesita almacenar en cada nodo es una etiqueta de distancia y su elemento principal. Cuando vea por primera vez cada nodo durante la búsqueda, lo etiquetará tentativamente; es posible que más adelante encuentre una mejor ruta hacia él, pero todo lo que tiene que actualizar en ese punto son las etiquetas de distancia y de los padres para ese único nodo.

Una vez que la etiqueta de forma permanente su destino, puede detener, y entonces se puede obtener la ruta óptima al mismo por subir las etiquetas de los padres de vuelta a la fuente.

Espero que ayude :)

Answer 6

Esta respuesta puede ser demasiado tarde para ti pero ofrecerlo en caso de que sea de ayuda a los demás.

primer lugar es necesario aclarar si

1. los bordes entre los nodos tienen diferentes pesos
2. la gráfica es dirigido o no dirigido

Han pasado 25 años desde que he estudiado este tipo de algoritmos en la universidad, pero por memoria, el algoritmo de Warshall es más fácil de implementar por el método de la matriz. Puede mirar aquí: www.ugrad.cs.ubc.ca/~cs490/Spring05/notes/graph_part3.pdf].