En un grafo dirigido (digraph), las aristas tienen una dirección (A → B ≠ B → A). En un grafo ponderado, cada arista lleva un (distancia, tiempo, capacidad). La combinación de ambos modela sistemas reales donde las relaciones son unidireccionales y tienen un costo.
Weighted directed graph:
A --5--> B
A --2--> C
C --1--> B
Adjacency list with weights:
A: [(B,5), (C,2)]
B: []
C: [(B,1)]
graph = {
'A': [('B', 5), ('C', 2)], # directed, weighted edges
'B': [],
'C': [('B', 1)],
}
# Shortest A->B is A->C->B = 2 + 1 = 3, not the direct edge 5.
| Dominio | Vértices | Aristas dirigidas ponderadas |
|---|---|---|
| Mapas / GPS | intersecciones | calles de un solo sentido + tiempo de viaje |
| Redes | routers | enlaces + latencia/ancho de banda |
| Programación de tareas | tareas | dependencias + duraciones |
| Finanzas | monedas | tipos de cambio |
| Objetivo | Algoritmo | Complejidad |
|---|---|---|
| Camino más corto (pesos no negativos) | Dijkstra | O((V+E) log V) |
| Camino más corto (aristas negativas) | Bellman-Ford | O(VE) |
| Ordenamiento con dependencias | Topological sort | O(V+E) |
| Detectar ciclos / alcanzabilidad | DFS | O(V+E) |
La dirección y el peso son lo que convierten un grafo abstracto en un modelo fiel de problemas de enrutamiento, programación y dependencia que impulsan aplicaciones reales.
La elección del algoritmo depende de estas propiedades — por ejemplo, los pesos negativos descartan Dijkstra y requieren Bellman-Ford.