Лабораторная работа IX «Взвешенные графы: маршруты и остов»
Продолжение раздела «Графы».
Обязательная часть:
-
алгоритм Дейкстры;
-
восстановление кратчайшего пути;
-
работа с положительными весами.
Вариант повышенной сложности:
-
Bellman–Ford;
-
Floyd–Warshall;
-
Prim;
-
Kruskal.
Практическая модель:
вершины — склады или торговые точки;
ребро — транспортный маршрут;
вес — стоимость, время или расстояние.
Нужно найти:
-
оптимальный маршрут;
-
его стоимость;
-
все расстояния из источника;
-
при дополнительном задании — минимальный остов инфраструктуры.
Студент должен объяснить, почему BFS не заменяет Дейкстру на произвольном взвешенном графе.