Взвешенные графы
Рёбрам присвоены веса (стоимость, расстояние, время). Алгоритмы кратчайшего пути: Дейкстра (1956, O(V²)), Беллман-Форд (1958, отрицательные веса), Floyd-Warshall (все пары, 1962). Применение: GPS-навигация, сетевая маршрутизация.
Взвешенные графы
Кратчайшие пути и ограничения
Выбор алгоритма кратчайшего пути зависит от структуры весов: Дейкстра для неотрицательных рёбер, Беллман—Форд для произвольных, Флойд—Уоршелл для всех пар. Это основа маршрутизации и логистики.
Минимальные остовные деревья
Для взвешенных графов, кроме кратчайших путей, важна задача построения минимального остова. Алгоритмы Прима и Краскала дают разные стратегии выбора рёбер при одинаковой целевой функции.