L'algorithme du meilleur chemin le plus court

Question

Quelle est la différence entre le "Algorithme Floyd-Warshall" y "Algorithme de Dijkstra" et lequel est le meilleur pour trouver le chemin le plus court dans un graphe ?

Je dois calculer le chemin le plus court entre toutes les paires d'un réseau et enregistrer les résultats dans un tableau comme suit :

**A     B     C     D      E**
A 0     10    15    5     20
B 10     0    5     5     10
C 15     5    0     10    15
D 5      5    10    0     15
E 20     10    15   15    0

Answer 1

Dijkstra L'algorithme de l'auteur trouve le chemin le plus court entre un nœud et tous les autres nœuds du graphe. On l'exécute une fois pour chaque nœud. Les poids doivent être non négatifs, donc si nécessaire vous devez d'abord normaliser les valeurs dans le graphe.

Floyd-Warshall calcule les chemins les plus courts entre toutes les paires de nœuds en une seule fois ! Les poids des cycles doivent être non-négatifs, et le graphe doit être dirigé (votre schéma ne l'est pas).

Johnson L'algorithme d'Erika utilise l'algorithme de Dijkstra pour trouver toutes les paires en un seul passage, et est plus rapide pour les arbres épars (voir le lien pour l'analyse).

Answer 2

Floyd Warshall trouve les chemins entre toutes les paires de sommets, mais Dijkstra ne trouve que le chemin d'un sommet à tous les autres.

Floyd Warshall est O(|V|) 3 ) et Dikstra est O(|E| + |V| log |V|) mais vous devrez l'exécuter V fois pour trouver toutes les paires, ce qui donne une complexité de O(|E * V| + |V 2 | log |V|) je suppose. Cela signifie qu'il est peut-être plus rapide d'utiliser Dijsktra de manière répétée que l'algorithme FW. Je voudrais essayer les deux approches et voir laquelle est la plus rapide dans le cas réel.

Answer 3

Dijkstra trouve le chemin le plus court à partir de seulement un vertex, Floyd-Warshall le trouve entre tous d'entre eux.

Answer 4

Utilisez l'algorithme de Floyd-Warshall si vous voulez trouver le plus court chemin entre tous paires de sommets, car son temps d'exécution est (beaucoup) plus élevé que celui de l'algorithme de Dijkstra.

L'algorithme de Floyd-Warshall a une performance de O(|V|) dans le pire des cas. 3 ), alors que la méthode de Dijkstra a une performance pire de O(|E| + |V|log |V|).

Answer 5

L'algorithme de Dijkstra sert principalement à trouver le plus court chemin d'une seule paire, c'est-à-dire d'un nœud à tous les autres nœuds, tandis que celui de Floyd-Warshall sert à trouver le plus court chemin de toutes les paires, c'est-à-dire le plus court chemin entre toutes les paires de sommets. L'algorithme de Floyd-Warshall a une performance de O(|V|3) dans le pire des cas, alors que celui de Dijkstra a une performance de O(|E| + |V|log |V|) dans le pire des cas. De plus, l'algorithme de Dijkstra ne peut pas être utilisé pour des poids négatifs (nous utilisons Bellmann Ford pour cela), mais pour Floyd-Warshall, nous pouvons utiliser des poids négatifs mais pas de cycles négatifs.