Este grupo de trabajo ha estado mucho tiempo investigando la respuesta a tu búsqueda, te compartimos la respuesta por esto deseamos que te resulte de mucha ayuda.
Solución:
Se puede aplicar a ambos. He aquí por qué:
Un no dirigido El gráfico es básicamente lo mismo que un dirigido gráfico con bidireccional conexiones (= dos conexiones en direcciones opuestas) entre los nodos conectados.
Entonces, realmente no tiene que hacer nada para que funcione para un gráfico no dirigido. Solo necesita conocer todos los nodos a los que se puede acceder desde cada nodo dado a través de, por ejemplo, un lista de adyacencia.
Puede usar el algoritmo de Dijkstra en gráficos dirigidos y no dirigidos, porque simplemente agrega bordes nodos en PriorityQueue cuando tiene un borde al que viajar desde su lista de adyacencia. Por ejemplo, si uno de mis nodos tiene un borde de A a B de peso 3, entonces, si se dirige desde BI, no podrá agregar el borde nuevamente a A, mientras que AI podría agregarlo a B.
Al igual que las otras respuestas, asegúrese de no confundirlo con pesos. El algoritmo de Dijkstra se ejecuta en gráficos ponderados positivos; de lo contrario, la cola de prioridad sería inútil.
En su ejemplo, el algoritmo de Dijkstra funcionaría porque el gráfico se pesa (positivamente) y tiene bordes dirigidos.
La falla habría sido que los bordes se han asignado dos veces en forma de un gráfico no dirigido. Debe tener cuidado al analizar los bordes al principio en sus objetos para no duplicar los bordes en la lista de adyacencia.
Un gráfico dirigido solo significa que los bordes que conectan los vértices pueden conectarse de una manera, pero no de la otra. Esto significa que un vértice puede ser adyacente a otro, pero ese otro vértice puede no ser adyacente al primer vértice.
En el contexto del algoritmo de Dijkstra, no importa si el gráfico es dirigido o no. El algoritmo de Dijkstra simplemente hace referencia a los vértices adyacentes de un vértice. Es esta lista de adyacencia la que tendría que modificar si estuviera cambiando un gráfico de dirigido a no dirigido.