Algoritmos de GrafosAdvanced

Algoritmo de Floyd-Warshall

Algoritmo de caminos más cortos entre todos los pares que calcula distancias entre cada par de vértices en tiempo O(V³). Usa programación dinámica con lógica central elegante de tres líneas. Maneja pesos negativos y proporciona cierre transitivo. Ideal para grafos densos, análisis de redes y cuando se necesitan todas las distancias por pares.

#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 Algoritmos de Grafos

Búsqueda en Anchura (BFS)

Intermediate

Explora un grafo nivel por nivel, visitando todos los vértices en la profundidad actual antes de avanzar más profundo. Usa una cola y es ideal para encontrar caminos más cortos en grafos no ponderados. Las aplicaciones incluyen resolución de laberintos, análisis de redes sociales y encontrar conexiones entre nodos.

Búsqueda en Profundidad (DFS)

Intermediate

Explora un grafo yendo lo más profundo posible a lo largo de cada camino antes de retroceder. Se implementa usando una pila o recursión, lo que lo hace natural para problemas recursivos. Se usa para búsqueda de caminos, detección de ciclos, ordenamiento topológico y generación de laberintos.

Algoritmo de Dijkstra

Advanced

Encuentra los caminos más cortos desde un vértice fuente único a todos los demás vértices en un grafo ponderado. Impulsa sistemas de navegación GPS y protocolos de enrutamiento de redes. Funciona eficientemente con pesos de arista no negativos usando un enfoque codicioso con una cola de prioridad.

Back to Algoritmos de Grafos