Hola, soy nuevo en esto, ¿alguien podría ayudarme?

R

Ahora estoy trabajando en la implementación del método de Dijkstra para un problema de recorrido de gráficos, pero tengo problemas para resolverlo. Recibo resultados incorrectos para la ruta más corta a pesar de seguir las etapas del algoritmo y utilizar una cola de prioridad para la selección de nodos.

Un error específico que estoy experimentando tiene que ver con la forma en que ajusto las longitudes entre los nodos vecinos. Aquí hay un ejemplo de mi código:

for neighbor in graph[node]:
    new_distance = distances[node] + edge_weight(node, neighbor)
    if new_distance < distances[neighbor]:
        distances[neighbor] = new_distance
        priority_queue.push(neighbor, new_distance)

Revisé el código varias veces y leí sitios web como scaler para ver si estoy en el camino correcto, pero no puedo averiguar qué está causando el problema. Las distancias parecen estar incorrectamente actualizadas y este error se propaga a lo largo del algoritmo, lo que resulta en rutas más cortas inexactas.

Me pregunto si hay una falla lógica en mi código que me falta. ¿Podría estar haciendo algo mal al calcular la nueva distancia o al actualizar las distancias en la matriz de distancias? ¿Es posible que haya manejado la cola de prioridad incorrectamente?

Agradecería cualquier idea o recomendación sobre cómo superar este error y garantizar que las distancias se actualicen correctamente durante la ejecución del algoritmo de Dijkstra. ¡Gracias por su ayuda!"

desu

8
B

Lo único que se me ocurre a bote pronto es que la prioQ te esté ordenando los nodos en orden inverso, que estés usando una tupla (neighb, distance) y esté usando la ID del nodo como criterio de ordenación y la distancia como tie breaker cuando debería ser al revés

Si no es eso pues ni puta idea, a priori parece correcto más o menos

S

#1 priority_queue.push(neighbor, new_distance)
Tiene que ser

priority_queue.push(new_distance, neighbor)

Estas ordenando primero por node_id y depues por distancia.

Usuarios habituales