Algoritmo de Dijkstra C ++

El algoritmo de Dijkstra también se conoce como el algoritmo de ruta más corto posible. Es el procedimiento encontrar la ruta más corta entre los nodos/ bordes del gráfico. El gráfico más corto de un árbol se crea comenzando desde el vértice de origen a todos los demás puntos en el gráfico.

Algoritmo

• Antes de la implementación directa del gráfico Dijkstra en el lenguaje de programación C ++, necesitamos comprender el funcionamiento de este algoritmo de gráfico.
• El primer paso es la creación de "sptset", que se abrevia como el conjunto de árboles de ruta más corto; almacena el registro de esos vértices que se incluyen en la ruta más corta. En la etapa inicial, este conjunto se declara como nulo.
• En el siguiente paso, primero, todos estos valores en los nodos se declaran como infinitos, ya que no sabemos el peso de los caminos hasta ahora.
• Elija un vértice "u" que no esté presente ya en sptset y es de valor mínimo. Luego inclúyalo a sptset. Después de eso, actualice los valores de distancia de todos esos nodos que son vértices adyacentes de "U."Todo esto se hace debajo del bucle hasta que SPTSet puede contener todos los vértices.

Implementación del algoritmo gráfico de Dijkstra

Aquí está la implementación del gráfico Dijkstra, donde se escribe un programa para la representación de la matriz de adyacencia de ese gráfico. Comience el programa agregando dos bibliotecas muy esenciales para el logro del programa en lenguaje de programación C ++ que nos hace capaces de usar funciones CIN y Cout.

#incluir
#incluir

Después de describir las bibliotecas, ahora proporcionaremos el tamaño o los vértices del gráfico en el que necesitamos la ruta más corta. Hemos dado 9 vértices, lo que significa que la matriz es un cuadrado de [9] [9].

#Define V 9

"V" es para los vértices. Como el algoritmo requiere muchos pasos para lograr la tarea proporcionada, cada paso o proceso se divide en funciones separadas para realizarlas de modo que el código sea claro y no hay ambigüedad con respecto a la lógica. Además, la complejidad también se elimina.

La función se crea aquí para buscar el vértice que tiene un valor de distancia mínima; Contiene el conjunto de vértices que no están incluidos en el árbol que tiene el camino más corto. La función contendrá la matriz de distancia y un sptset de tipo bool, el conjunto de árbol de ruta más corto y la matriz como parámetro de la función. Dentro de la función, el valor mínimo se inicializa declarando una variable de tipo entero que almacenará el valor devuelto. Se introducen dos variables, max y el min_index.

Int min = int_max, min_index;

A For Loop se usa aquí; en el que se toma un vértice inicial en todos los vértices, el bucle continuará hasta que se atraviesen todos los vértices. Aquí se aplica una condición usando una declaración IF que verifica si el conjunto de ruta más corto es falso medios, está vacía en este momento y la distancia del vértice es menor que la del valor mínimo del vértice, que se declara anteriormente, Luego, asigne el valor actual del vértice como min, y el min_index también contendrá el mismo valor del vértice.

Min = dist [v], min_index = v;

Después de calcular el valor mínimo del vértice, el siguiente es el proceso de crear una función que mostrará la matriz de distancia que se construyó anteriormente. Un bucle iterará cada índice que se accederá y se mostrará. Primero, el número de vértice se muestra a partir del valor cero, y la distancia del vértice desde la fuente también se menciona aquí con una secuencia. Esta función se declara aquí, pero se llamará más adelante en el programa cuando toda la ruta se calcule como la distancia más corta.

La parte principal de todo el código fuente se declara ahora, donde se calcula la implementación de la ruta más corta. Un gráfico estará representado por la representación de la matriz de adyacencia. Esta función tomará una matriz gráfica y la fuente como valores de parámetros que actuarán como entrada para el cálculo de la distancia. Primero, dentro de la función, declararemos la matriz de salida que contendrá la ruta más corta desde la fuente hasta un punto específico. En segundo lugar, se declara una matriz de variables booleanas, que devolverá verdadero si el vértice se incluye en la determinación de la ruta más corta al comienzo.

Int dist [v]; bool sptset [v];

Todas las distancias se establecerán como infinitas, y la matriz de ruta del árbol más corta es falsa. Con la ayuda de un bucle, todo este proceso tendrá lugar.

Dentro del bucle, el vértice de distancia mínima se recoge del conjunto de vértices que aún no se procesan. En la primera iteración, 'u' siempre es igual al vértice de origen.

Int u = Mindistance (dist, sptset);

Los vértices que se eligen y atraviesan se eligen y marcan como se procesan al establecer la variable booleana es verdadero.

sptset [u] = true;

Cuando se agrega un vértice, todos los vértices adyacentes a ese vértice en particular también se verifican; Esto necesita una actualización. Por lo tanto, actualizaremos el valor de "dist" de los vértices adyacentes de esos vértices que han sido piquete hasta ahora.

Dentro de esto para el bucle, actualizaremos Dist [v] si y solo si no está en el sptset, hay una línea llamada borde del vértice U a V, y el peso total de la ruta que comienza desde "SRC" "V" pasando a través de "U" es más pequeño que el valor actual presente en el Dist [V].

Dist [v] = dist [u] + gráfico [u] [v];

Después de eso, la función de impresión que hemos declarado anteriormente se llama al pasar la matriz Dist [] como parámetro.

printsolution (dist);

En el programa principal, creamos un gráfico de matriz 9*9. Y luego, se realiza la llamada de función para la función Dijkstra, a través de la cual se pasa el gráfico.

Guardar todo el código. Compile el código usando un compilador G ++ en el terminal Ubuntu. '-o' es un símbolo que guarda la salida del archivo.

$ G ++ -O DIJ DIJ.C
ps ./Dij

Puede ver que todos los vértices en cada línea separada se muestran junto con la distancia de cada vértice desde la fuente.

Este código ayuda a calcular la distancia más corta, pero no admite calcular la información sobre la ruta. Este código fuente es bueno para los gráficos no dirigidos, pero también puede ser posible usar para los gráficos dirigidos. Al usar este código, podemos encontrar la distancia más corta desde el punto de fuente hasta todos los demás vértices en el gráfico.

La complejidad del tiempo del gráfico Dijkstra

Hablaremos sobre la complejidad del tiempo de la implementación. Es:

0 (V^2).

Esto se puede reducir a 0 (E log v) utilizando el proceso del montón binario. El gráfico Dijkstra no es para los gráficos que tienen pesos negativos.

Conclusión

Este artículo contiene el proceso de encontrar la distancia más corta entre el nodo fuente al resto de los nodos. Puede haber muchos enfoques para esto. Pero el gráfico Dijkstra es uno de los mejores mecanismos para este propósito. Está diseñado para gráficos no dirigidos. Hemos explicado el proceso paso a paso con el código fuente para hacerlo vívido para los nuevos usuarios. Esperamos que este esfuerzo esté a la altura de los lectores.