Em um grafo direcionado (digraph), as arestas têm uma direção (A → B ≠ B → A). Em um grafo ponderado, cada aresta carrega um (distância, tempo, capacidade). A combinação de ambos modela sistemas reais onde relacionamentos são unidirecionais e têm um custo.
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.
| Domínio | Vértices | Arestas direcionadas ponderadas |
|---|---|---|
| Mapas / GPS | interseções | estradas de mão única + tempo de viagem |
| Redes | roteadores | links + latência/largura de banda |
| Agendamento de tarefas | tarefas | dependências + durações |
| Finanças | moedas | taxas de câmbio |
| Objetivo | Algoritmo | Complexidade |
|---|---|---|
| Caminho mais curto (pesos não negativos) | Dijkstra | O((V+E) log V) |
| Caminho mais curto (arestas negativas) | Bellman-Ford | O(VE) |
| Ordenação com dependências | Topological sort | O(V+E) |
| Detectar ciclos / alcançabilidade | DFS | O(V+E) |
Direção e peso são o que transformam um grafo abstrato em um modelo fiel de roteamento, agendamento e problemas de dependência que impulsionam aplicações reais.
A escolha do algoritmo depende dessas propriedades — por exemplo, pesos negativos descartam Dijkstra e exigem Bellman-Ford.