Ai-je raison sur les différences entre les algorithmes Floyd-Warshall, Dijkstra et Bellman-Ford?

16

J'ai étudié les trois et j'énonce mes inférences ci-dessous. Quelqu'un pourrait-il me dire si je les ai suffisamment compris ou non? Je vous remercie.

  1. L'algorithme de Dijkstra est utilisé uniquement lorsque vous avez une seule source et que vous souhaitez connaître le plus petit chemin d'un nœud à un autre, mais échoue dans des cas comme celui-ci .

  2. L'algorithme Floyd-Warshall est utilisé lorsque tous les nœuds peuvent être une source, vous voulez donc que la distance la plus courte atteigne n'importe quel nœud de destination à partir de n'importe quel nœud source. Cela échoue uniquement lorsqu'il y a des cycles négatifs.

  3. Bellman-Ford est utilisé comme Dijkstra, quand il n'y a qu'une seule source. Cela peut gérer des poids négatifs et son fonctionnement est le même que Floyd-Warshall, sauf pour une seule source, non? (C'est celui dont je suis le moins sûr.)

algorithms graph-theory Raphael
la source
Bienvenue! J'ai édité les parties de code redondantes; les gens peuvent cliquer sur Wikipedia par eux-mêmes, ou vérifier les algorithmes dans leurs manuels préférés. Notez que votre question est bizarre à poser, car une réponse «oui» ne peut rien comprendre de plus.
Raphael

Réponses:

23

L'algorithme de Dijkstra n'est utilisé que lorsque vous avez une seule source et que vous voulez connaître le plus petit chemin d'un nœud à un autre, mais échoue [dans les graphiques avec des bords négatifs]

ssprevious[v]v

Le comportement de l'algorithme de Dijkstra dans les graphiques à bords négatifs dépend de la variante précise en discussion. Certaines variantes de l'algorithme, comme celle de Wikipedia, s'exécutent toujours rapidement mais ne calculent pas correctement les chemins les plus courts lorsqu'il y a des bords négatifs. D'autres variantes, comme celle de ces notes de cours, calculent toujours les chemins les plus courts correctement (sauf s'il y a un cycle négatif accessible depuis la source) mais peuvent nécessiter un temps exponentiel dans le pire des cas s'il y a des bords négatifs.

L'algorithme de Floyd-Warshall est utilisé lorsque tous les nœuds peuvent être une source, vous voulez donc que la distance la plus courte atteigne n'importe quel nœud de destination à partir de n'importe quel nœud source. Cela échoue uniquement lorsqu'il y a des cycles négatifs.

C'est correct. Floyd-Warshall est un exemple d' algorithme de chemin le plus court toutes paires , ce qui signifie qu'il calcule les chemins les plus courts entre chaque paire de nœuds. Un autre exemple est "pour chaque nœud v, exécutez Dijkstra avec v comme nœud source". Il y en a plusieurs autres.

Bellman-Ford est utilisé comme Dijkstra, lorsqu'il n'y a qu'une seule source. Cela peut gérer les poids négatifs et son fonctionnement est le même que celui de Floyd-Warshall, sauf pour une source, non?

Bellman-Ford est un autre exemple d'un algorithme à chemin unique à source unique , comme Dijkstra. Bellman-Ford et Floyd-Warshall sont similaires - par exemple, ce sont tous deux des algorithmes de programmation dynamique - mais Floyd-Warshall n'est pasO(V3)O(V2E)O(VE)

Pour plus de détails, consultez votre manuel d'algorithmes préféré. (Vous avez un manuel d'algorithmes préféré, n'est-ce pas?)

JeffE
la source
Pourriez-vous partager votre manuel d'algorithmes préféré?
Abdul
2
@Abdul algorithms.wtf
JeffE
@Abdul appâté. - Le manuel utilisé au MIT / Stanford est T. Cormen, et al. Introduction aux algorithmes. Le manuel utilisé à Cornell est J. Kleinberg, et al Algorithm Design. cs.sjtu.edu.cn/~jiangli/teaching/CS222/files/materials/…
AffluentOwl
2

Les trois algorithmes sont couverts dans les diapositives de la conférence par le professeur Jaehyun Park (Stanford University). Voici le lien Algorithmes de chemin le plus court

Jitendra
la source
Cela ne répond pas à la question sur les différences et n'est pas autonome, juste un lien sans résumé ne compte pas comme une bonne réponse. Il semble également redondant, car il ne couvre pas plus que les réponses existantes.
Mal
1

La page Wikipedia sur le problème du chemin le plus court décrit deux problèmes différents: SSSP et APSP.

Chemin le plus court à source unique (SSSP):

  • Algorithme de Dijkstra: résout le problème du chemin le plus court à source unique.
    • Contraintes: seules les arêtes négatives ne peuvent pas être gérées.
    • Graphes non pondérés: Dijkstra est identique à BFS.

  • Algorithme Bellman-Ford: résout le problème à source unique si les poids des bords peuvent être négatifs. Il s'agit d'une amélioration sur Dijkstra où il est désormais capable de gérer également les poids négatifs.

Chemin le plus court pour toutes les paires (APSP):

  • Algorithme Floyd-Warshall: résout toutes les paires de chemins les plus courts. Gère les bords positifs et négatifs.
    • Contraintes: ne peut pas gérer les cycles négatifs.

Par conséquent, Floyd – Warshall n'est pas la même chose que BFS, bien que la méthodologie sous-jacente soit la même, la programmation dynamique.

Fooo
la source
1

Peut-être que cela devrait être un commentaire plutôt qu'une réponse, mais c'est une distinction entre ces algorithmes que les autres réponses ne mentionnent pas.

Les gens ont tendance à appeler l'algorithme de Floyd Floyd-Warshall , mais les algorithmes de Floyd et Warshall ne sont pas les mêmes.

O(1)O(n2)

reinierpost
la source