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

L'algorithme de Prim construit un arbre à portée minimale pour le graphe, qui est un arbre qui relie tous les nœuds du graphe et dont le coût total est le plus faible parmi tous les arbres qui relient tous les nœuds. Cependant, la longueur d'un chemin entre deux nœuds dans le MST peut ne pas être le chemin le plus court entre ces deux nœuds dans le graphe original. Les MST sont utiles, par exemple, si l'on voulait connecter physiquement les nœuds du graphe 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, puisque tout ce qui compte, c'est qu'ils soient connectés.

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

Une autre différence importante concerne les types de graphes sur lesquels les algorithmes travaillent. L'algorithme de Prim ne fonctionne que sur les graphes non orientés, puisque le concept de TMS suppose que les graphes sont intrinsèquement non orientés. (Il existe ce qu'on appelle une "arborescence d'envergure minimale" pour les graphes dirigés, mais les algorithmes pour les trouver sont beaucoup plus compliqués). L'algorithme de Dijkstra fonctionnera parfaitement sur les graphes dirigés, puisque les arbres des plus courts chemins peuvent effectivement être dirigés. De plus, l'algorithme de Dijkstra ne donne pas nécessairement la solution correcte dans les graphes contenant des poids d'arêtes négatifs alors que l'algorithme de Prim peut le faire.

J'espère que cela vous aidera !

Answer 2

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

Considérons ce graphique

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

Le chemin le plus court est le 9, tandis que le MST est un "chemin" différent au 10.

Answer 3

Les algorithmes Prim et Dijkstra sont presque identiques, à l'exception de la "fonction de relaxation".

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, il s'agit de la fonction de relaxation.

• Le Prim, qui recherche l'arbre couvrant le minimum, ne s'intéresse qu'au minimum du total des arêtes couvrant tous les sommets. La fonction relax est alt = w(u,v)
• La fonction Dijkstra, qui recherche la longueur minimale du chemin, et qui se soucie donc de l'accumulation des bords. La fonction de relaxation est alt = w(u,v) + u.key

Answer 4

L'algorithme de Dijsktra trouve la distance minimum du noeud i à tous les noeuds (vous spécifiez i). En retour, vous obtenez l'arbre à distance minimale du nœud i.

L'algorithme Prims permet d'obtenir l'arbre à portée minimale. pour un graphique donné . Un arbre qui relie tous les nœuds alors que la somme de tous les coûts est la plus faible possible.

Donc avec Dijkstra vous pouvez aller du nœud sélectionné à n'importe quel autre avec le coût minimum vous n'obtenez pas cela avec les Prim's.

Answer 5

La seule différence que je vois est que l'algorithme de Prim stocke un bord de coût minimum alors 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 tel que le coût est minimal. L'algorithme de Prim, quant à lui, vous donne un arbre d'envergure minimale tel que tous les nœuds sont connectés et que le coût total est minimal.

En termes simples :

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