algorithm
El algoritmo de Dijkstra

Algoritmo de la ruta más corta de Dijkstra

Antes de continuar, se recomienda tener una breve idea sobre la matriz de adyacencia y BFS

El algoritmo de Dijkstra se conoce como algoritmo de ruta más corta de una sola fuente. Se utiliza para encontrar las rutas más cortas entre nodos en un gráfico, que pueden representar, por ejemplo, redes de carreteras. Fue concebido por Edsger W. Dijkstra en 1956 y publicado tres años después.

Podemos encontrar la ruta más corta utilizando el algoritmo de búsqueda de búsqueda de amplitud (BFS). Este algoritmo funciona bien, pero el problema es que asume que el costo de atravesar cada ruta es el mismo, lo que significa que el costo de cada borde es el mismo. El algoritmo de Dijkstra nos ayuda a encontrar la ruta más corta donde el costo de cada ruta no es el mismo.

Al principio veremos cómo modificar BFS para escribir el algoritmo de Dijkstra, luego agregaremos una cola de prioridad para convertirlo en un algoritmo completo de Dijkstra.

Digamos que la distancia de cada nodo desde la fuente se mantiene en la matriz d [] . Como en, d [3] representa que el tiempo d [3] se toma para llegar al nodo 3 desde la fuente . Si no conocemos la distancia, almacenaremos el infinito en d [3] . Además, deje que el costo [u] [v] represente el costo de uv . Eso significa que cuesta [u] [v] pasar de u nodo a v nodo.

Necesitamos entender la relajación del borde. Digamos que desde su casa, esa es la fuente , se necesitan 10 minutos para ir al lugar A. Y se tarda 25 minutos en ir al lugar B. Tenemos,

d[A] = 10
d[B] = 25

Ahora digamos que se necesitan 7 minutos para ir desde el lugar A al lugar B , eso significa:

cost[A][B] = 7

Luego podemos ir al lugar B desde la fuente yendo al lugar A desde la fuente y luego desde el lugar A , yendo al lugar B , que tomará 10 + 7 = 17 minutos, en lugar de 25 minutos. Asi que,

d[A] + cost[A][B] < d[B]

Luego actualizamos,

d[B] = d[A] + cost[A][B]

Esto se llama relajación. Iremos del nodo u al nodo v y si d [u] + costo [u] [v] <d [v] luego actualizaremos d [v] = d [u] + costo [u] [v] .

En BFS, no necesitamos visitar ningún nodo dos veces. Solo verificamos si un nodo es visitado o no. Si no fue visitado, pusimos el nodo en la cola, lo marcamos como visitado e incrementamos la distancia en 1. En Dijkstra, podemos empujar un nodo en la cola y, en lugar de actualizarlo, visitamos, relajamos o actualizamos el nuevo borde. Veamos un ejemplo:

Supongamos que el Nodo 1 es la Fuente . Entonces,

d[1] = 0
d[2] = d[3] = d[4] = infinity (or a large value)

Configuramos, d [2], d [3] yd [4] al infinito porque todavía no sabemos la distancia. Y la distancia de la fuente es, por supuesto, 0 . Ahora, vamos a otros nodos desde la fuente y si podemos actualizarlos, los pondremos en la cola. Digamos por ejemplo, vamos a atravesar el borde 1-2 . Como d [1] + 2 <d [2], lo que hará que d [2] = 2 . De manera similar, atravesaremos el borde 1-3, lo que hace que d [3] = 5 .

Podemos ver claramente que 5 no es la distancia más corta que podemos cruzar para ir al nodo 3 . Así que atravesar un nodo solo una vez, como BFS, no funciona aquí. Si vamos del nodo 2 al nodo 3 usando el borde 2-3 , podemos actualizar d [3] = d [2] + 1 = 3 . Entonces podemos ver que un nodo puede ser actualizado muchas veces. Cuantas veces preguntas El número máximo de veces que se puede actualizar un nodo es el número de grados de un nodo.

Veamos el pseudo-código para visitar cualquier nodo varias veces. Simplemente modificaremos BFS:

procedure BFSmodified(G, source):
Q = queue()
distance[] = infinity
Q.enqueue(source)
distance[source]=0
while Q is not empty
    u <- Q.pop()
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
        end if
    end for
end while
Return distance

Esto se puede usar para encontrar la ruta más corta de todos los nodos desde la fuente. La complejidad de este código no es tan buena. Este es el por qué,

En BFS, cuando pasamos del nodo 1 a todos los demás nodos, seguimos el método de primer orden de llegada . Por ejemplo, fuimos al nodo 3 desde la fuente antes de procesar el nodo 2 . Si vamos al nodo 3 desde la fuente , actualizamos el nodo 4 como 5 + 3 = 8 . Cuando volvamos a actualizar el nodo 3 desde el nodo 2 , necesitamos actualizar el nodo 4 como 3 + 3 = 6 nuevamente. Así que el nodo 4 se actualiza dos veces.

Dijkstra propuso, en lugar de ir por el método Primero en llegar, primero en servir , si actualizamos los nodos más cercanos primero, entonces tomará menos actualizaciones. Si hubiéramos procesado el nodo 2 antes, entonces el nodo 3 se habría actualizado antes, y después de actualizar el nodo 4 en consecuencia, ¡obtendríamos fácilmente la distancia más corta! La idea es elegir de la cola, el nodo, que está más cerca de la fuente . Así que usaremos la cola de prioridad aquí para que cuando abramos la cola, nos traiga el nodo más cercano u desde la fuente . ¿Cómo va a hacer eso? Verificará el valor de d [u] con él.

Veamos el pseudo-código:

procedure dijkstra(G, source):
Q = priority_queue()
distance[] = infinity
Q.enqueue(source)
distance[source] = 0
while Q is not empty
    u <- nodes in Q with minimum distance[]
    remove u from the Q
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
            Q.enqueue(v)
        end if
    end for
end while
Return distance

El pseudocódigo devuelve la distancia de todos los demás nodos desde la fuente . Si queremos conocer la distancia de un solo nodo v , simplemente podemos devolver el valor cuando v se extrae de la cola.

Ahora, ¿el algoritmo de Dijkstra funciona cuando hay una ventaja negativa? Si hay un ciclo negativo, entonces ocurrirá un bucle infinito, ya que seguirá reduciendo el costo cada vez. Incluso si hay una ventaja negativa, Dijkstra no funcionará, a menos que regresemos justo después de que se haga estallar el objetivo. Pero entonces, no será un algoritmo de Dijkstra. Necesitaremos el algoritmo de Bellman-Ford para procesar el borde / ciclo negativo.

Complejidad:

La complejidad de BFS es O (log (V + E)) donde V es el número de nodos y E es el número de bordes. Para Dijkstra, la complejidad es similar, pero la clasificación de la cola de prioridad toma O (logV) . Entonces la complejidad total es: O (Vlog (V) + E)

A continuación se muestra un ejemplo de Java para resolver el algoritmo de ruta más corta de Dijkstra usando la matriz de adyacencia

import java.util.*;
import java.lang.*;
import java.io.*;

class ShortestPath
{
    static final int V=9;
    int minDistance(int dist[], Boolean sptSet[])
    {
        int min = Integer.MAX_VALUE, min_index=-1;

        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }

        return min_index;
    }

    void printSolution(int dist[], int n)
    {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++)
            System.out.println(i+" \t\t "+dist[i]);
    }

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

        Boolean sptSet[] = new Boolean[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }

        dist[src] = 0;

        for (int count = 0; count < V-1; count++)
        {
            int u = minDistance(dist, sptSet);

            sptSet[u] = true;

            for (int v = 0; v < V; v++)

                if (!sptSet[v] && graph[u][v]!=0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u]+graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }

        printSolution(dist, V);
    }

    public static void main (String[] args)
    {
    int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
                                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                                {0, 0, 2, 0, 0, 0, 6, 7, 0}
                                };
        ShortestPath t = new ShortestPath();
        t.dijkstra(graph, 0);
    }
}

La salida esperada del programa es

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14