algorithm
L'algorithme de Dijkstra

Algorithme du plus court chemin de Dijkstra

Avant de continuer, il est recommandé d'avoir une brève idée de la matrice d'adjacence et de la BFS

L'algorithme de Dijkstra est connu sous le nom d'algorithme à source unique le plus court. Il est utilisé pour trouver les chemins les plus courts entre les nœuds dans un graphique, qui peuvent représenter, par exemple, des réseaux routiers. Il a été conçu par Edsger W. Dijkstra en 1956 et publié trois ans plus tard.

Nous pouvons trouver le chemin le plus court en utilisant l’algorithme de recherche Breadth First Search (BFS). Cet algorithme fonctionne bien, mais le problème est que cela suppose que le coût de traverser chaque chemin est le même, ce qui signifie que le coût de chaque bord est le même. L'algorithme de Dijkstra nous aide à trouver le chemin le plus court où le coût de chaque chemin n'est pas le même.

Au début, nous verrons comment modifier BFS pour écrire l'algorithme de Dijkstra, puis nous ajouterons une file d'attente prioritaire pour en faire un algorithme complet de Dijkstra.

Disons que la distance de chaque noeud de la source est conservée dans le tableau d [] . Comme dans, d [3] représente le temps d [3] pour atteindre le nœud 3 depuis la source . Si nous ne connaissons pas la distance, nous allons stocker l' infini dans d [3] . Aussi, laissez le coût [u] [v] représenter le coût de uv . Cela signifie qu'il prend coût [u] [v] pour aller du noeud u au noeud v.

Nous devons comprendre Edge Relaxation. Disons que de chez vous, c'est la source , il faut 10 minutes pour aller au lieu A. Et il faut 25 minutes pour aller au lieu B. Nous avons,

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

Maintenant, disons qu'il faut 7 minutes pour aller du lieu A au lieu B , cela signifie:

cost[A][B] = 7

Ensuite, nous pouvons aller placer B à partir de la source en allant placer A à partir de la source , puis à partir de la position A , en passant à la position B , qui prendra 10 + 7 = 17 minutes au lieu de 25 minutes. Alors,

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

Ensuite, nous mettons à jour,

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

Cela s'appelle la relaxation. Nous irons du noeud u au noeud v et si d [u] + cost [u] [v] <d [v] alors nous mettrons à jour d [v] = d [u] + cost [u] [v] .

Dans BFS, nous n'avons pas eu besoin de visiter deux nœuds. Nous avons seulement vérifié si un nœud est visité ou non. Si elle n'était pas visitée, nous avons poussé le nœud dans la file d'attente, marqué comme visité et incrémenté la distance de 1. Dans Dijkstra, nous pouvons pousser un nœud dans la file d'attente et au lieu de le mettre à jour, nous relâchons ou mettons à jour le nouveau bord. Regardons un exemple:

Supposons que le nœud 1 soit la source . Alors,

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

Nous définissons, d [2], d [3] et d [4] à l' infini car nous ne connaissons pas encore la distance. Et la distance de la source est bien sûr 0 . Maintenant, nous allons à d'autres nœuds à partir de la source et si nous pouvons les mettre à jour, nous les enverrons dans la file d'attente. Disons par exemple, nous allons traverser le bord 1-2 . Comme d [1] + 2 <d [2] qui fera d [2] = 2 . De même, nous traverserons l' arête 1-3, ce qui rend d [3] = 5 .

Nous pouvons clairement voir que 5 n'est pas la distance la plus courte que nous pouvons traverser pour aller au nœud 3 . Donc, traverser un nœud une seule fois, comme BFS, ne fonctionne pas ici. Si nous passons du nœud 2 au nœud 3 en utilisant l' arête 2-3 , nous pouvons mettre à jour d [3] = d [2] + 1 = 3 . Nous pouvons donc voir qu'un nœud peut être mis à jour plusieurs fois. Combien de fois demandez-vous? Le nombre maximal de fois qu'un nœud peut être mis à jour est le nombre de degrés d'un nœud.

Voyons le pseudo-code pour visiter n'importe quel noeud plusieurs fois. Nous allons simplement modifier 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

Cela peut être utilisé pour trouver le chemin le plus court de tous les nœuds de la source. La complexité de ce code n'est pas si bonne. Voici pourquoi,

En BFS, lorsque nous passons du nœud 1 à tous les autres nœuds, nous suivons la méthode du premier arrivé, premier servi . Par exemple, nous sommes allés au nœud 3 de la source avant de traiter le nœud 2 . Si nous allons au noeud 3 de la source , nous mettons à jour le noeud 4 en 5 + 3 = 8 . Lorsque nous mettons à jour le nœud 3 à partir du nœud 2 , nous devons mettre à jour le nœud 4 en tant que 3 + 3 = 6 ! Ainsi, le nœud 4 est mis à jour deux fois.

Dijkstra a proposé, au lieu de choisir la méthode du premier arrivé, premier servi , si nous mettons à jour les nœuds les plus proches en premier, alors il faudra moins de mises à jour. Si nous traitions le nœud 2 auparavant, alors le nœud 3 aurait été mis à jour avant et après avoir mis à jour le nœud 4 en conséquence, nous obtiendrions facilement la distance la plus courte! L'idée est de choisir dans la file d'attente, le nœud le plus proche de la source . Nous allons donc utiliser la file d' attente prioritaire ici de sorte que lorsque nous sautons la file d' attente, il nous apportera le nœud le plus proche de la source u. Comment ça va faire ça? Il vérifiera la valeur de d [u] avec elle.

Voyons le pseudo-code:

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

Le pseudo-code renvoie la distance de tous les autres noeuds de la source . Si nous voulons connaître la distance d'un seul nœud v , nous pouvons simplement renvoyer la valeur lorsque v est sorti de la file d'attente.

L'algorithme de Dijkstra fonctionne-t-il maintenant lorsqu'il y a un bord négatif? S'il y a un cycle négatif, la boucle infinie se produira, car elle réduira le coût à chaque fois. Même s'il y a un avantage négatif, Dijkstra ne fonctionnera pas, à moins que nous ne revenions juste après le déclenchement de la cible. Mais ce ne sera pas un algorithme de Dijkstra. Nous aurons besoin de l'algorithme Bellman – Ford pour traiter les fronts / cycles négatifs.

Complexité:

La complexité de BFS est O (log (V + E)) où V est le nombre de nœuds et E est le nombre d'arêtes. Pour Dijkstra, la complexité est similaire, mais le tri de la file d'attente prioritaire prend O (logV) . La complexité totale est donc: O (Vlog (V) + E)

Vous trouverez ci-dessous un exemple Java pour résoudre l'algorithme du plus court chemin de Dijkstra à l'aide de la matrice d'adjacence.

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);
    }
}

Le résultat attendu du programme est

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