Différence entre l'algorithme de Prim et celui de Dijkstra ?

Question

Quelle est la différence exacte entre l'algorithme de Dijkstra et celui de Prim ? Je sais que l'algorithme de Prim donne un MST mais l'arbre généré par Dijkstra sera également un MST. Alors quelle est la différence exacte ?

Answer 1

Les deux peuvent être mis en œuvre 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, passez f = w(u, v) et pour la passe de Dijkstra f = u.key + w(u, v) .

Un autre point intéressant est que le générique ci-dessus peut également mettre en œuvre la recherche BFS (Breadth First Search), même si cela serait excessif car une file d'attente prioritaire coûteuse n'est pas vraiment nécessaire. Pour transformer l'algorithme Generic ci-dessus en BFS, passez f = u.key + 1 ce qui revient à appliquer la valeur 1 à tous les poids (c'est-à-dire que BFS donne le nombre minimum d'arêtes nécessaires pour aller du point A au point B).

Intuition

Voici une bonne façon de penser à l'algorithme générique ci-dessus : Nous commençons avec deux seaux A et B. Initialement, nous mettons tous nos sommets dans B pour que le seau 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 avec les sommets de B. Nous choisissons une arête en utilisant certains critères parmi ces arêtes de croisement et déplaçons le sommet correspondant de B vers A. Répétez ce processus jusqu'à ce que B soit vide.

Une façon brute d'implémenter cette idée serait de maintenir une file d'attente prioritaire des arêtes pour les sommets de A qui traversent vers B. Évidemment, cela serait problématique si le graphe n'est pas clairsemé. La question serait donc de savoir si l'on peut plutôt maintenir une file d'attente prioritaire des sommets ? En fait, c'est possible puisque notre décision finale est de choisir le sommet de B.

Contexte historique

Il est intéressant de noter que la version générique de la technique qui sous-tend les deux algorithmes est conceptuellement aussi vieille que 1930, même si les ordinateurs électroniques n'existaient pas encore.

L'histoire commence avec Otakar Borůvka qui avait besoin d'un algorithme pour un ami de la famille qui essayait de comprendre comment relier les villes du pays de Moravie (qui fait maintenant partie de la République tchèque) avec des lignes électriques à coût minimal. Il a publié son algorithme en 1926 dans une revue de mathématiques, l'informatique n'existant pas encore à 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 aujourd'hui sous le nom d'algorithme de Prim, qui l'a redécouvert en 1957.

Indépendamment de tout cela, en 1956, Dijkstra devait écrire un programme pour démontrer les capacités d'un nouvel ordinateur que son institut avait développé. Il pensait qu'il serait cool que l'ordinateur trouve 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 (parce que son ordinateur était de 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 pas encore de revues d'informatique et qu'il pensait que ce n'était pas très important. L'année suivante, il a découvert le problème de la connexion des terminaux des nouveaux ordinateurs de manière à minimiser la longueur des fils. Il réfléchit à ce problème et redécouvre l'algorithme de Jarník/Prim qui utilise à nouveau la même technique que l'algorithme du plus court chemin qu'il avait découvert un an auparavant. Il mentionné que ses deux algorithmes ont été conçus sans utiliser de papier ni de crayon. En 1959, il a publié les deux algorithmes dans un papier qui ne fait que 2 pages et demie.

Answer 2

Dijkstra trouve le chemin le plus court entre le nœud de départ et le nœud d'arrivée. et tous les autres noeuds. En retour, vous obtenez l'arbre à distance minimale depuis le nœud de départ, c'est-à-dire que vous pouvez atteindre tous les autres nœuds aussi efficacement que possible.

L'algorithme Prims permet d'obtenir 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 la plus faible 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 le temps de déplacement et le carburant.
2. Prim veut savoir comment déployer efficacement un système ferroviaire, c'est-à-dire économiser les coûts de matériel.

Answer 3

Directement à partir de Algorithme de Dijkstra article de wikipedia :

Le processus qui sous-tend l'algorithme de Dijkstra est similaire au processus d'avidité utilisé dans l'algorithme de Prim. L'objectif de Prim est de trouver un arbre d'envergure minimale qui relie tous les nœuds du graphe ; Dijkstra ne s'intéresse qu'à deux nœuds. L'algorithme de Prim n'évalue pas le poids total du chemin à partir du nœud de départ, mais uniquement le chemin individuel.

Answer 4

J'ai été dérangé par la même question dernièrement, 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 censés résoudre, à savoir le plus court chemin entre deux nœuds et l'arbre de recouvrement minimal (MST). Le formel est de trouver le plus court chemin entre, disons, le nœud s y t et une exigence rationnelle est de visiter chaque bord du graphe au plus une fois. Cependant, il ne PAS nous obligent à visiter tous les nœuds. La dernière (MST) consiste à nous faire visiter TOUTES le nœud (au plus une fois), et avec la même exigence rationnelle de visiter chaque arête au plus une fois également.

Ceci étant dit, Dijkstra nous permet de "prendre un raccourci" tant que je peux aller de s a t sans se préoccuper des conséquences - une fois que j'aurai atteint t J'ai fini ! Bien qu'il existe également un chemin de s a t dans le MST, mais cette 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 d'accès au réseau. s - t chemin trouvé par l'algorithme de Dijstra. Voici un exemple rapide avec 3 noeuds :

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

Disons que chacune des arêtes supérieures a un coût de 2, et que l'arête inférieure a un coût de 3, alors Dijktra nous dira de prendre le chemin inférieur, puisque nous ne nous soucions pas du nœud central. D'un autre côté, Prim nous renverra une MST avec les deux arêtes supérieures, en éliminant l'arête inférieure.

Cette différence se reflète également dans la différence subtile entre les implémentations : dans l'algorithme de Dijkstra, il est nécessaire d'avoir une étape de tenue de livre (pour chaque nœud) afin de mettre à jour le chemin le plus court à partir de s après avoir absorbé un nouveau nœud, alors que dans l'algorithme de Prim, ce n'est pas nécessaire.

Answer 5

L'explication la plus simple est Dans Prims, vous ne spécifiez pas le nœud de départ. Mais dans le cas de la dijsktra, vous devez trouver le chemin le plus court entre le nœud donné et tous les autres nœuds (vous devez avoir un nœud de départ).