Algorithmes de grapheAdvanced

Algorithme de Floyd-Warshall

Algorithme de plus courts chemins entre toutes les paires qui calcule les distances entre chaque paire de sommets en temps O(V³). Utilise la programmation dynamique avec une logique centrale élégante de trois lignes. Gère les poids négatifs et fournit la fermeture transitive. Idéal pour les graphes denses, l'analyse de réseau et quand toutes les distances par paires sont nécessaires.

#graph#all-pairs-shortest-paths#dynamic-programming#transitive-closure

Complexity Analysis

Time (Average)

O(V³)

Expected case performance

Space

O(V²)

Memory requirements

Time (Best)

O(V³)

Best case performance

Time (Worst)

O(V³)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 25•Section 25.2

Number of Vertices (3-6)

Adjacency Matrix (use ∞ for infinity)

Each row on a new line, comma-separated

Example Graphs:

How it works

• All-pairs shortest paths algorithm
• Uses dynamic programming approach
• O(V³) time, O(V²) space complexity
• Handles negative edge weights
• Formula: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Algorithmes de graphe

Parcours en largeur (BFS)

Intermediate

Explore un graphe niveau par niveau, visitant tous les sommets à la profondeur actuelle avant d'aller plus profondément. Utilise une file d'attente et est idéal pour trouver les chemins les plus courts dans les graphes non pondérés. Les applications incluent la résolution de labyrinthes, l'analyse de réseaux sociaux et la recherche de connexions entre nœuds.

Parcours en profondeur (DFS)

Intermediate

Explore un graphe en allant aussi profondément que possible le long de chaque chemin avant de revenir en arrière. Implémenté à l'aide d'une pile ou de la récursion, ce qui le rend naturel pour les problèmes récursifs. Utilisé pour la recherche de chemins, la détection de cycles, le tri topologique et la génération de labyrinthes.

Algorithme de Dijkstra

Advanced

Trouve les chemins les plus courts d'un sommet source unique vers tous les autres sommets dans un graphe pondéré. Alimente les systèmes de navigation GPS et les protocoles de routage réseau. Fonctionne efficacement avec des poids d'arêtes non négatifs en utilisant une approche gloutonne avec une file de priorité.

Back to Algorithmes de graphe