Кратчайшие пути в сети
1. Связный граф G с неотрицательными весами задан списком смежных вершин. Найдите медиану графа G. (Медиана графа - такая вершина графа, что сумма расстояний от нее до остальных вер-шин минимальна).
2. Задан орграф G с неотрицательными весами. Постройте по нему последовательность графов G i с тем же множеством вершин, что и у графа G. Ребро между вершинами в G i проводится тогда, когда расстояние между соответствующими вершинами в G не превышает S=i+Длина_кратчайшего_пути .
3. Задан орграф G с неотрицательными весами, заданными матрицей. Найдите вершины, длины кратчайших путей до ко-торых от выделенного источника равны.
4. Задан орграф G с неотрицательными весами, заданными матрицей A[ u,v ]. Найдите кратчайший путь от источника S до выделенной вершины T. Для этого найти по алгоритму Дейкстры расттояния D[ v ] от S до прочих вершин графа. Затем найти вершину V, такую, что D[ t ]=D[ v ]+A[ v,t ]. Это предпоследняя вершина пути. Предыдущая вершина пути u ищется из условия D[ v ]=D[ u ]+D[ u,v ] и т.д. до тех пор, пока не найдется первая вершина пути.
5. Задан взвешенный граф Е (дугам графа приписаны веса - вещественные числа). Определить, существуют ли два пути одинаковой длины из i-ой вершины в j-ю (написать рекурсивную функцию, определяющую количество путей заданной длины между двумя вершинами).
