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

L'algorithme de Prim construit un arbre de couverture minimum pour le graphe, qui est un arbre qui connecte tous les noeuds dans le graphe et a le moins de coût total parmi tous les arbres qui connectent tous les noeuds. Cependant, la longueur d'un chemin entre deux noeuds dans le MST pourrait ne pas être le chemin le plus court entre ces deux noeuds dans le graphe original. MSTs sont utiles, par exemple, si vous souhaitez installer les nœuds dans le graphe pour fournir de l'électricité à le moindre coût total. Peu importe que la longueur du chemin entre deux noeuds ne soit pas optimale, puisque tout ce qui vous intéresse est le fait qu'ils soient connectés.

L'algorithme de Dijkstra construit un arbre de chemin le plus court à partir d'un noeud source. Un arbre de chemin le plus court est un arbre qui connecte tous les noeuds dans le graphe au noeud source et a la propriété que la longueur de n'importe quel chemin du noeud source à n'importe quel autre noeud dans le graphe est minimiser. Ceci est utile, par exemple, si vous voulez construire un réseau routier qui fait d'aussi efficace que possible pour tout le monde certains grands jalon important. Cependant, l'arbre le plus court n'est pas garanti d'être un arbre couvrant minimum, et le coût de construction d'un tel arbre pourrait être beaucoup plus grand 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 des graphiques non dirigés, puisque le concept D'un DSPM suppose que les graphiques sont intrinsèquement non dirigés. (Il y a quelque chose appelé "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 les plus courts peuvent en effet être dirigés. De plus, L'algorithme de Dijkstra ne fournit pas nécessairement la bonne solution dans les graphiques contenant des poids de bord négatifs , tandis que L'algorithme de Prim pouvez gérer cela.

Espérons que cette aide!

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

considérons ce graphique

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

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

Prim et l'algorithme de Dijkstra sont presque identiques, à 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) and w(u,v) < v.key

                    v.parent = u
                    v.key = w(u,v)    <== relax function, Pay attention here

}

Dans 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) and w(u,v) < v.key

                    v.parent = u
                    v.key = w(u,v) + u.key  <== relax function, Pay attention here

}

la seule différence est la dernière ligne du code, qui est la fonction relax. Le Prim, qui recherche l'arbre couvrant le minimum, ne se soucie que du minimum des arêtes totales couvrant tous les sommets. on dirait donc: v. key = w(u, v) Le Dijkstra, qui recherche pour la longueur minimale du chemin, donc il se soucie de l'accumulation de bord. On dirait donc :v. key = w (u,v) + U. clé

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

L'algorithme

Prims vous donne le MST pour un graphe donné, c'est-à-dire un arbre qui connecte tous les noeuds alors que la somme de tous les coûts est le minimum possible.

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

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

directement de algorithme de Dijkstra article Wikipédia:

le processus qui sous-tend L'algorithme de Dijkstra est similaire au processus cupide utilisé dans L'algorithme de Prim. Le but de Prim est de trouver un arbre de couverture minimum qui connecte tous les noeuds dans le graphe; Dijkstra est concerné avec seulement deux noeuds. Prim's n'évalue pas le poids total du chemin à partir du noeud de départ, mais seulement le chemin individuel.

la principale différence entre les algorithmes de base réside dans leurs différents critères de sélection de bord. En général, ils utilisent tous les deux une file d'attente prioritaire pour sélectionner les noeuds suivants, mais ont des critères différents pour sélectionner les noeuds adjacents des noeuds de traitement actuels: L'algorithme de Prim exige que les noeuds adjacents suivants soient également maintenus 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 vertex.distance sont les deuxième point différent.

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

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

vous initialisez Prim avec un vertex source, s , i.e., Prim.new(s) ; s peut être n'importe quel vertex, et indépendamment de s , le résultat final, qui sont les bords de l'arbre couvrant minimum (MST) sont les mêmes. Pour obtenir les bords MST, nous appelons la méthode edges() .

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

la première distinction est que L'algorithme de Dijkstra résout un problème différent que Kruskal et Prim. Dijkstra résout le problème du chemin le plus court (à partir d'un noeud spécifié), tandis que Kruskal et Prim trouvent un arbre couvrant le coût minimum. Ce qui suit est une forme modifiée d'une description que j'ai écrite à cette page: algorithmes de graphe.

Pour tout graphe, spanning tree est un ensemble d'arêtes suffisante pour fournir exactement un chemin entre chaque paire de sommets. Ce restriction signifie qu'il ne peut y avoir de circuits formés par les bords choisis.

un arbre couvrant un coût minimal est celui dont le poids total est le plus faible possible (où le poids représente le coût ou la distance). Il pourrait y avoir plus d'un arbre de ce genre, mais Prim et Kruskal sont tous deux garantis de trouver l'un d'eux.

pour un vertex spécifié (disons X), l'arbre de chemin le plus court est un arbre couvrant tel que le chemin de X à tout autre vertex est aussi court que possible (c.-à-d. ayant le poids minimal possible).

Prim et Dijkstra "grandir" l'arbre à partir d'un sommet de départ. En d'autres termes, ils ont un accent "local"; à chaque étape, nous ne considérons que les bords adjacents aux sommets précédemment choisis, en choisissant l'option la moins chère qui répond à nos besoins. Pendant ce temps, Kruskal est un algorithme "global", ce qui signifie que chaque bord est (greedily) choisi à partir de l'ensemble du graphe. (En fait, Dijkstra pourrait être considérée comme ayant un aspect global, comme indiqué ci-dessous.)

Pour trouver un coût minimum spanning tree:

Kruskal( approche globale): à chaque étape, Choisissez le bord disponible le moins cher n'importe où qui ne viole pas l'objectif de créer un arbre couvrant. Prim (approche locale): choisissez un vertex de départ. À chaque étape successive, choisissez le bord disponible le moins cher attaché à n'importe quel vertex précédemment choisi qui ne viole pas l'objectif de créer un arbre couvrant. Pour trouver un plus court chemin de découpage arbre:

Dijkstra: à chaque étape, Choisissez le bord attaché à n'importe quel vertex précédemment choisi (l'aspect local) qui rend la distance totale du vertex de départ (l'aspect global) aussi petit que possible, et ne viole pas l'objectif de créer un arbre couvrant.

les Arbres À coût Minimum et les Arbres À chemin le plus court sont facilement confondus, tout comme les algorithmes de Prim et de Dijkstra qui les résolvent. Les deux algorithmes "grandissent" à partir du vertex de départ, à chaque pas choisir un bord qui connecte un vertex Y qui est dans l'arbre à un vertex Z qui ne l'est pas. Cependant, tandis que Prim choisit le bord le moins cher, Dijkstra choisit le bord qui résulte dans le chemin le plus court de X à Z.

une simple illustration est utile pour comprendre la différence entre ces algorithmes et les arbres qu'ils produisent. Dans le graphique ci-dessous, à partir du sommet A, Prim et Dijkstra commencent par choisir edge AB, puis Ajouter edge BD. Voici là où les deux algorithmes divergent: Prim complète l'arbre en ajoutant edge DC, tandis que Dijkstra ajoute AC ou BC, parce que les chemins A-C et A-B-C (tous deux avec la distance totale 30) sont plus courts que le chemin A-B-D-C (la distance totale 31).

algorithme de Dijkstras n'est utilisé que pour trouver le chemin le plus court.

Dans Minimum Spanning tree(Prim ou de Kruskal algorithme de) vous obtenir le minimum de rebords avec un minimum de bord de valeur.

par exemple:- considérez une situation où vous ne voulez pas créer un réseau énorme pour lequel u aura besoin d'un grand nombre de fils de sorte que ce comptage de fils peut être fait en utilisant Arbre de enjambement Minimum(Prim's or Algorithme de Kruskal) (I. e il vous donnera le nombre minimum de fils pour créer une connexion réseau câblée énorme avec un coût minimum).

alors que " algorithme de Dijkstras " sera utilisé pour obtenir le chemin le plus court entre deux noeuds tout en connectant les noeuds entre eux.