Spanning Tree vs le plus court chemin

Quelle est la différence entre l'algorithme minimum Spanning Tree et un algorithme de chemin le plus court?

Dans ma classe de structures de données, nous avons traité deux algorithmes de spanning-tree minimum (Prim et Kruskal) et un algorithme de chemin le plus court (Dijkstra).

Spanning Tree minimum est un arbre dans un graphique qui couvre tous les sommets et le poids total d'un arbre est minimal. Le plus court chemin est assez évident, c’est le plus court chemin d’un sommet à un autre.

Ce que je ne comprends pas, c’est que le Spanning Tree minimum a un poids total minimal, les chemins dans l’arbre ne seraient-ils pas les chemins les plus courts? Quelqu'un peut-il expliquer ce que je manque?

Toute aide est appréciée.

Considérons le graphe triangulaire avec des poids unitaires - il a trois sommets et les trois arêtes ont le poids . Le chemin le plus court entre deux sommets est le chemin direct, mais si vous les mettez tous ensemble, vous obtenez un triangle plutôt qu'un arbre. Chaque collection de deux arêtes forme un arbre recouvrant minimum dans ce graphique, cependant si (par exemple) vous choisissez , alors vous manquez le chemin le plus court .$x,y,z$$\{x,y\},\{x,z\},\{y,z\}$$1$$\{x,y\},\{y,z\}$$\{x,z\}$

En conclusion, si vous mettez tous les chemins les plus courts ensemble, vous n’obtenez pas nécessairement un arbre.

Vous avez raison de dire que les deux algorithmes de Dijkstra (chemins les plus courts d'un seul nœud de démarrage) et Prim (arbre couvrant d' épaisseur minimale à partir d'un nœud donné) ont une structure très similaire. Ils sont à la fois gourmands (prennent le meilleur avantage du point de vue actuel) et construisent un arbre couvrant le graphique.

La valeur qu'ils minimisent cependant est différente. Dijkstra sélectionne comme bord suivant celui qui mène de l’arbre à un nœud qui n’a pas encore été choisi le plus près du nœud de départ. (Ensuite, avec ce choix, les distances sont recalculées.) Prim choisit comme bord le plus court menant à l’arbre construit jusqu’à présent. Ainsi, les deux algorithmes ont choisi un "bord minimal". La principale différence est la valeur choisie pour être minimale. Pour Dijkstra, il s'agit de la longueur du chemin complet du nœud de départ au nœud candidat. Pour Prim, il s'agit simplement du poids de cette arête unique.

Pour voir la différence, vous devriez essayer de construire quelques exemples pour voir ce qui se passe. C'est vraiment instructif. L’exemple le plus simple montrant un comportement différent est un triangle avec des arêtes et de longueur 2, tandis que a une longueur de 1. À partir de Dijkstra choisira et (donnant deux chemins de longueur 2) tandis que Prim choisit et (donnant le spanning tree de poids 3).$x,y,z$$\{x,y\}$$\{x,z\}$$\{y,z\}$$x$$\{x,y\}$$\{x,z\}$$\{x,y\}$$\{y,z\}$

En ce qui concerne Kruskal , c'est légèrement différent. Il résout l'arborescence minimale, mais lors de l'exécution, il choisit les arêtes qui ne peuvent pas former d'arbre, elles évitent simplement les cycles. Les solutions partielles peuvent donc être déconnectées. À la fin, vous obtenez un arbre.

Bien que le calcul des algorithmes Minimum Spanning Tree et Shortest Path soit similaire, il se concentre sur deux exigences différentes.

Dans MST, il est nécessaire d’atteindre chaque sommet (une arborescence graphique) une fois et le coût total (collectif) pour atteindre chaque sommet doit être minimal entre toutes les combinaisons possibles.

Dans Shortest Path, l'exigence consiste à atteindre le sommet de destination à partir du sommet source avec le coût le plus bas possible (poids le plus faible). Nous n’avons donc pas à nous soucier d’atteindre chaque sommet, mais nous concentrons uniquement sur les sommets source et cible et c’est là que réside la différence.

Voici l'exemple pour expliquer pourquoi MST ne donne pas nécessairement le chemin le plus court entre 2 sommets.

(A)----5---(B)----5---(C)
 |                     |
 |----------7----------| 

Dans le cas MST, les bords AB. BC sera sur MST avec un poids total de 10. Le coût pour atteindre de A à C dans MST est donc de 10.

Mais dans le cas du plus court chemin, le plus court chemin entre A et C est AC, qui est 7. AC n'a jamais été sur MST.

La différence réside dans le but ultime de cet algorithme.

Dijkstra's - Ici, l'objectif est d'atteindre du début à la fin. Vous n'êtes préoccupé que par ces 2 points et optimisez votre parcours en conséquence.

Krusal's - Ici, vous pouvez commencer à tout moment et visiter tous les autres points du graphique. Vous ne pouvez donc pas toujours choisir le chemin le plus court pour deux points. Au lieu de cela, l'objectif est de choisir le chemin qui vous mènera à un chemin plus court pour tous les autres points.

Je pense qu'un exemple le rendra plus clair.

Le Spanning Tree ressemble à celui ci-dessous. En effet, si nous additionnons les arêtes dans cette configuration, nous obtenons le coût total le plus bas possible : 2 + 5 + 14 + 4 = 25.

(1)   (4)
  \   /
   (2)
  /   \
(3)   (5)

En observant le Spanning Tree, vous pourriez penser à tort que cela vous donne les chemins les plus courts, mais en pratique, ce n'est pas le cas. Par exemple, si nous voulions passer d'un nœud (1)à un autre, (4)cela nous coûterait 7. Cependant, si nous utilisions l'algorithme de Dijkstra sur le graphe d'origine, nous constaterions que nous pouvons passer directement d'un nœud (1)à (4)un coût de 5.

Exemple pratique pour montrer la différence>

Supposons que vous arrivez en train en ville et que vous souhaitiez vous rendre à votre hôtel.

Option 1: Prendre un taxi: Le taxi empruntera le chemin le plus court pour vous rendre à l’hôtel depuis la gare. Si le conducteur doit suivre un chemin le long de l’arbre de chemin le plus court centré sur la station.

Option 2: prendre un bus. La compagnie de bus veut s'occuper des gens, pas seulement de vous. Le chemin idéal prendrait tous les points clés de la ville. Donc, il suivra (*) un chemin le long de l'arbre minimal. C'est pourquoi l'autobus est plus lent, mais comme les coûts sont partagés, c'est moins cher.

(*) En fait, les gens se plaindraient si le Spanning Tree minimum était utilisé (le trajet en bus serait trop long). Donc, dans la pratique, ce serait une solution mixte utilisant un arbre alpha (à mi-chemin entre un arbre couvrant minimal et un arbre avec le plus court chemin).

Ils sont basés sur deux propriétés différentes. Le Spanning Tree minimum est basé sur la propriété cut alors que le plus court chemin est basé sur la propriété relaxante des bords.

Une coupe divise un graphique en deux composants. Cela peut impliquer plusieurs arêtes. En MST, nous sélectionnons l'arête ayant le moins de poids.

La relaxation des bords indique que, étant donné que je connais la distance entre A et B: dist (a, b) et dist entre A et C: dist (a, c), si dist (a, b) + arête (b, c) est inférieure à dist (a, c), alors je peux me détendre bord (ac). Après avoir relaxé tous les bords, nous obtenons le chemin le plus court.

Je recommande fortement de regarder la vidéo sur les algorithmes de graphes du professeur Robert Sedgewick.