В ориентированном графе (digraph) рёбра имеют направление (A → B ≠ B → A). В взвешенном графе каждое ребро несёт (расстояние, время, пропускная способность). Комбинация обоих моделирует реальные системы, где отношения односторонние и имеют стоимость.
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.
| Область | Вершины | Взвешенные ориентированные рёбра |
|---|---|---|
| Карты / GPS | перекрёстки | дороги с односторонним движением + время в пути |
| Сети | маршрутизаторы | каналы связи + задержка/пропускная способность |
| Планирование задач | задачи | зависимости + длительность |
| Финансы | валюты | курсы обмена |
| Цель | Алгоритм | Сложность |
|---|---|---|
| Кратчайший путь (неотрицательные веса) | Dijkstra | O((V+E) log V) |
| Кратчайший путь (отрицательные рёбра) | Bellman-Ford | O(VE) |
| Сортировка с зависимостями | Topological sort | O(V+E) |
| Обнаружение циклов / достижимость | DFS | O(V+E) |
Направление и вес — это то, что превращает абстрактный граф в точную модель задач маршрутизации, планирования и управления зависимостями, которые лежат в основе реальных приложений.
Выбор алгоритма зависит от этих свойств — например, отрицательные веса исключают Dijkstra и требуют Bellman-Ford.