Différence entre les algorithmes de Prim et de Dijkstra?

Quelle est la différence exacte entre les algorithmes de Dijkstra et Prim? Je sais que Prim's donnera un MST, mais l'arbre généré par Dijkstra sera également un MST. Alors quelle est la différence exacte?

L'algorithme de Prim construit un arbre couvrant minimum pour le graphique, qui est un arbre qui connecte tous les nœuds du graphique et qui a le coût total le moins élevé parmi tous les arbres qui connectent tous les nœuds. Cependant, la longueur d'un chemin entre deux nœuds quelconques dans le MST peut ne pas être le chemin le plus court entre ces deux nœuds dans le graphique d'origine. Les MST sont utiles, par exemple, si vous souhaitez câbler physiquement les nœuds du graphique pour leur fournir de l'électricité au moindre coût total. Peu importe que la longueur du chemin entre deux nœuds ne soit pas optimale, car tout ce qui vous importe est le fait qu'ils sont connectés.

L'algorithme de Dijkstra construit un arbre de chemin le plus court partir d'un nœud source. Un arbre de chemin le plus court est un arbre qui relie tous les nœuds du graphique au nœud source et a la propriété que la longueur de tout chemin du nœud source à tout autre nœud du graphique est minimisée. Ceci est utile, par exemple, si vous souhaitez construire un réseau routier qui permette à tout le monde de se rendre aussi efficace que possible vers un point de repère important. Cependant, il n'est pas garanti que l'arbre de chemin le plus court soit un arbre couvrant minimum, et la somme des coûts sur les bords d'un arbre de chemin le plus court peut être beaucoup plus grande que le coût d'un MST.

Une autre différence importante concerne les types de graphiques sur lesquels les algorithmes travaillent. L'algorithme de Prim ne fonctionne que sur les graphes non orientés, puisque le concept d'un MST suppose que les graphes sont intrinsèquement non orientés. (Il y a quelque chose qui s'appelle une "arborescence de couverture minimale" pour les graphes dirigés, mais les algorithmes pour les trouver sont beaucoup plus compliqués). L'algorithme de Dijkstra fonctionnera très bien sur les graphes dirigés, puisque les arbres de chemin les plus courts peuvent en effet être dirigés. De plus, l'algorithme de Dijkstra ne donne pas nécessairement la bonne solution dans les graphiques contenant des poids d'arête négatifs , alors que l'algorithme de Prim peut gérer cela.

J'espère que cela t'aides!

L'algorithme de Dijkstra ne crée pas de MST, il trouve le chemin le plus court.

Considérez ce graphique

       5     5
  s *-----*-----* t
     \         /
       -------
         9

Le chemin le plus court est 9, tandis que le MST est un `` chemin '' différent à 10.

Les algorithmes de Prim et Dijkstra sont presque les mêmes, à l'exception de la "fonction relax".

Prim:

MST-PRIM (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v)    <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Dijkstra:

Dijkstra (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v) + u.key  <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

La seule différence est signalée par la flèche, qui est la fonction relax.

• Le Prim, qui recherche l'arbre couvrant minimum, ne se soucie que du minimum des arêtes totales couvrant tous les sommets. La fonction relax estalt = w(u,v)
• Le Dijkstra, qui recherche la longueur minimale du chemin, donc il se soucie de l'accumulation des bords. La fonction relax estalt = w(u,v) + u.key

L'algorithme de Dijsktra trouve la distance minimale entre le nœud i et tous les nœuds (vous spécifiez i). Donc, en retour, vous obtenez l'arbre de distance minimale du nœud i.

L'algorithme Prims vous donne l'arborescence minimale pour un graphique donné . Un arbre qui relie tous les nœuds alors que la somme de tous les coûts est le minimum possible.

Donc, avec Dijkstra, vous pouvez passer du nœud sélectionné à n'importe quel autre avec le coût minimum , vous ne l'obtenez pas avec Prim's

La seule différence que je vois est que l'algorithme de Prim stocke une arête de coût minimum tandis que l'algorithme de Dijkstra stocke le coût total d'un sommet source au sommet actuel.

Dijkstra vous donne un chemin du nœud source au nœud de destination de sorte que le coût soit minimum. Cependant, l'algorithme de Prim vous donne un arbre couvrant minimum tel que tous les nœuds sont connectés et le coût total est minimum.

En termes simples:

Donc, si vous souhaitez déployer un train pour relier plusieurs villes, vous utiliserez l'algo de Prim. Mais si vous voulez passer d'une ville à une autre en économisant le plus de temps possible, vous utiliserez l'algo de Dijkstra.

Les deux peuvent être implémentés en utilisant exactement le même algorithme générique comme suit:

Inputs:
  G: Graph
  s: Starting vertex (any for Prim, source for Dijkstra)
  f: a function that takes vertices u and v, returns a number

Generic(G, s, f)
    Q = Enqueue all V with key = infinity, parent = null
    s.key = 0
    While Q is not empty
        u = dequeue Q
        For each v in adj(u)
            if v is in Q and v.key > f(u,v)
                v.key = f(u,v)
                v.parent = u

Pour Prim, passer f = w(u, v)et pour le col de Dijkstra f = u.key + w(u, v).

Une autre chose intéressante est que ci-dessus Generic peut également implémenter Breadth First Search (BFS) même si cela serait excessif car une file d'attente prioritaire coûteuse n'est pas vraiment nécessaire. Pour passer au-dessus de l'algorithme générique en BFS, passezf = u.key + 1 ce qui équivaut à appliquer tous les poids à 1 (c'est-à-dire que BFS donne le nombre minimum d'arêtes nécessaires pour traverser du point A à B).

Intuition

Voici une bonne façon de penser à l'algorithme générique ci-dessus: Nous commençons avec deux compartiments A et B. Au départ, placez tous vos sommets dans B afin que le compartiment A soit vide. Ensuite, nous déplaçons un sommet de B vers A. Maintenant, regardez toutes les arêtes des sommets de A qui se croisent vers les sommets de B. A. Répétez ce processus jusqu'à ce que B soit vide.

Un moyen brutal d'implémenter cette idée serait de maintenir une file d'attente prioritaire des arêtes pour les sommets de A qui croise vers B. Évidemment, ce serait gênant si le graphe n'était pas clairsemé. La question serait donc de savoir si nous pouvons plutôt maintenir la file d'attente prioritaire des sommets? En fait, nous pouvons, car notre décision est finalement de savoir quel sommet choisir parmi B.

Contexte historique

Il est intéressant de noter que la version générique de la technique derrière les deux algorithmes est conceptuellement aussi vieille que 1930, même lorsque les ordinateurs électroniques n'existaient pas.

L'histoire commence avec Otakar Borůvka qui avait besoin d'un algorithme pour un ami de la famille essayant de comprendre comment connecter les villes du pays de Moravie (qui fait maintenant partie de la République tchèque) avec des lignes électriques à coût minime. Il a publié son algorithme en 1926 dans une revue liée aux mathématiques, car l'informatique n'existait pas à l'époque. Cela a attiré l'attention de Vojtěch Jarník qui a pensé à une amélioration de l'algorithme de Borůvka et l'a publié en 1930. Il a en fait découvert le même algorithme que nous connaissons maintenant comme l'algorithme de Prim qui l'a redécouvert en 1957.

Indépendamment de tout cela, en 1956, Dijkstra avait besoin d'écrire un programme pour démontrer les capacités d'un nouvel ordinateur que son institut avait développé. Il a pensé que ce serait cool d'avoir un ordinateur pour trouver des connexions pour voyager entre deux villes des Pays-Bas. Il a conçu l'algorithme en 20 minutes. Il a créé un graphique de 64 villes avec quelques simplifications (car son ordinateur était 6 bits) et a écrit le code pour cet ordinateur de 1956. Cependant, il n'a pas publié son algorithme parce qu'il n'y avait principalement pas de revues informatiques et il pensait que cela n'était peut-être pas très important. L'année suivante, il a appris le problème de la connexion des terminaux de nouveaux ordinateurs de telle sorte que la longueur des fils soit minimisée. Il réfléchit à ce problème et redécouvrit Jarník / Prim ' s algorithme qui utilise à nouveau la même technique que l'algorithme de chemin le plus court qu'il avait découvert un an auparavant. Ila mentionné que ses deux algorithmes ont été conçus sans utiliser de stylo ni de papier. En 1959, il a publié les deux algorithmes dans un article de seulement 2 pages et demie.

Dijkstra trouve le chemin le plus court entre son nœud de début et tous les autres nœuds. Donc, en retour, vous obtenez l'arbre de distance minimum du nœud de départ, c'est-à-dire que vous pouvez atteindre tous les autres nœuds aussi efficacement que possible.

L'algorithme Prims vous donne le MST pour un graphe donné c'est-à-dire un arbre qui relie tous les nœuds alors que la somme de tous les coûts est le minimum possible.

Pour faire une histoire courte avec un exemple réaliste:

1. Dijkstra veut connaître le chemin le plus court vers chaque point de destination en économisant du temps et du carburant.
2. Prim veut savoir comment déployer efficacement un système ferroviaire, c'est-à-dire économiser sur les coûts de matériaux.

Directement de l' article wikipedia de Dijkstra's Algorithm :

Le processus qui sous-tend l'algorithme de Dijkstra est similaire au processus glouton utilisé dans l'algorithme de Prim. Le but de Prim est de trouver un arbre couvrant minimum qui relie tous les nœuds du graphe; Dijkstra ne concerne que deux nœuds. Prim's n'évalue pas le poids total du chemin à partir du nœud de départ, seulement le chemin individuel.

J'ai été dérangé par la même question ces derniers temps, et je pense que je pourrais partager ma compréhension ...

Je pense que la principale différence entre ces deux algorithmes (Dijkstra et Prim) réside dans le problème qu'ils sont conçus pour résoudre, à savoir le chemin le plus court entre deux nœuds et un arbre couvrant minimal (MST). Le formel est de trouver le chemin le plus court entre, disons, le nœud s et t , et une exigence rationnelle est de visiter chaque arête du graphe au plus une fois. Cependant, cela ne nous oblige PAS à visiter tous les nœuds. Ce dernier (MST) est de nous faire visiter TOUS les nœuds (au plus une fois), et avec la même exigence rationnelle de visiter chaque arête au plus une fois aussi.

Cela étant dit, Dijkstra nous permet de "prendre un raccourci" si longtemps que je peux passer de s à t , sans se soucier de la conséquence - une fois que j'arrive à t , j'ai terminé! Bien qu'il existe également un chemin de s à t dans le MST, mais ce chemin s - t est créé en tenant compte de tous les nœuds restants, par conséquent, ce chemin peut être plus long que le chemin s - t trouvé par l'algorithme de Dijstra. Voici un exemple rapide avec 3 nœuds:

                                  2       2  
                          (s) o ----- o ----- o (t)     
                              |               |
                              -----------------
                                      3

Disons que chacun des bords supérieurs a le coût de 2 et le bord inférieur a un coût de 3, alors Dijktra nous dira de prendre le chemin du bas, car nous ne nous soucions pas du nœud du milieu. D'autre part, Prim nous retournera un MST avec les 2 bords supérieurs, en supprimant le bord inférieur.

Cette différence se reflète également dans la différence subtile dans les implémentations: dans l'algorithme de Dijkstra, il faut avoir une étape de comptabilité (pour chaque nœud) pour mettre à jour le chemin le plus court de s , après avoir absorbé un nouveau nœud, alors que dans l'algorithme de Prim, il y a n'est pas un tel besoin.

La principale différence entre les algorithmes de base réside dans leurs différents critères de sélection des arêtes. En général, ils utilisent tous les deux une file d'attente prioritaire pour sélectionner les nœuds suivants, mais ont des critères différents pour sélectionner les nœuds adjacents des nœuds de traitement actuels: l'algorithme de Prim exige que les nœuds adjacents suivants soient également conservés dans la file d'attente, tandis que l'algorithme de Dijkstra ne le fait pas:

def dijkstra(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            ...

def prim(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            if v in q and weight(u, v) < v.distance:// <-------selection--------
            ...

Les calculs de la distance vertex sont le deuxième point différent.

L'algorithme de Dijkstra est un problème de chemin le plus court source unique entre les nœuds i et j, mais l'algorithme de Prim est un problème d'arbre couvrant minimal. Ces algorithmes utilisent un concept de programmation nommé `` algorithme glouton ''

Si vous vérifiez ces notions, veuillez visiter

1. Note de cours sur l'algorithme glouton: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf
2. Arbre couvrant minimum: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/20-mst.pdf
3. Chemin le plus court de source unique: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/21-sssp.pdf

Algorithme de Dijkstras est utilisé uniquement pour trouver le chemin le plus court.

Dans Minimum Spanning Tree (algorithme de Prim ou Kruskal), vous obtenez un minimum d'egdes avec une valeur de bord minimum.

Par exemple: - Considérez une situation où vous ne souhaitez pas créer un énorme réseau pour lequel vous aurez besoin d'un grand nombre de fils afin que ces comptages de fils puissent être effectués en utilisant Minimum Spanning Tree (algorithme de Prim ou Kruskal) (c'est-à-dire qu'il vous donner un nombre minimum de fils pour créer une énorme connexion réseau filaire avec un coût minimum).

Alors que "l'algorithme de Dijkstras" sera utilisé pour obtenir le chemin le plus court entre deux nœuds tout en connectant tous les nœuds entre eux.

L'explication la plus simple est que dans Prims, vous ne spécifiez pas le nœud de départ , mais dans dijsktra, vous (Besoin d'avoir un nœud de départ) devez trouver le chemin le plus court du nœud donné à tous les autres nœuds.

@templatetypedef a couvert la différence entre MST et le chemin le plus court. J'ai couvert la différence d'algorithme dans une autre réponse So en démontrant que les deux peuvent être implémentés en utilisant le même algorithme générique qui prend un paramètre de plus en entrée: la fonction f(u,v). La différence entre l'algorithme de Prim et Dijkstra est simplement que f(u,v)vous utilisez.

Au niveau du code, l'autre différence est l'API.

Vous initialisez Prim avec un sommet source, s , ie Prim.new(s),; s peut être n'importe quel sommet, et quel que soit s , le résultat final, qui sont les arêtes de l'arbre couvrant minimum (MST), est le même. Pour obtenir les arêtes MST, nous appelons la méthode edges().

Vous initialisez Dijkstra avec un sommet source, s , c'est-à-dire Dijkstra.new(s)que vous voulez obtenir le plus court chemin / distance à tous les autres sommets. Les résultats finaux, qui sont le chemin / distance le plus court entre s et tous les autres sommets; sont différents selon les s . Pour obtenir les chemins / distances les plus courts de s à n'importe quel sommet, v , nous appelons les méthodes distanceTo(v)et pathTo(v)respectivement.