También estoy tratando de aprender gráficos usando la ruta de Dijkstra y estoy usando este tutorial de geeks para geeks. Creo que entiendo cómo funciona el uso del peso para encontrar el camino más corto. Sin embargo, esto puede ser una tontería, pero no entiendo cómo encontrar el punto de destino mirando el código. o como son las 9 entradas

¿Por qué hay 9 entradas? ¿Puede funcionar con solo tres? ¿Y cómo sabe el programa dónde terminar?

0
Ian W 16 oct. 2018 a las 19:23

2 respuestas

La mejor respuesta

Por lo tanto, para abordar la primera mitad de su pregunta, no hay un "nodo de destino" predeterminado con el algoritmo de Dijsktra, más bien sólo un resultado final.

En este ejemplo del código GeeksforGeeks,

void dijkstra(int graph[V][V], int src) 

Podemos ver que el algoritmo quiere una matriz de todos los nodos y desde qué nodo comenzará. Cada nodo de esta matriz tiene 9 entradas que corresponden a la distancia dada de ese nodo desde cualquier otro nodo, donde un valor de 0 representa que no hay conexión. Por ejemplo, el nodo "0" tiene valores:

{0, 4, 0, 0, 0, 0, 0, 8, 0}

Lo que significa que el nodo 0 está a 4 unidades del nodo 1, a 8 unidades del nodo 7, y no tiene conexión o ES uno de los otros 7 nodos. Si solo tiene 3 nodos, entonces usaría 3 entradas para representar las posibles distancias entre los 3.

Cuando el programa haya agotado todos los nodos y rutas posibles, el algoritmo se detendrá. Este algoritmo busca un árbol de expansión mínimo, no una ruta desde el punto A al punto B.

0
T. Douglass 16 oct. 2018 a las 17:04

El programa en ese ejemplo finaliza cuando se han visitado todos los nodos, no elige un destino específico. Calcula la distancia mínima (y la ruta) desde el nodo 0 hasta cada nodo del gráfico.

Hay 9 nodos en el ejemplo, pero, por supuesto, también puede usar 3 nodos o 1000 nodos.

0
JonasAnon 16 oct. 2018 a las 16:42