Условие задачи
Дан взвешенный граф G. Найти кратчайший путь между вершинами графа x6 и x1 методом Дейкстра. Он заключается в том, что вершинам графа присваиваются временные метки, которые затем по определенным правилам заменяются на постоянные метки.
Ответ
Алгоритм Дейкстры: 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине 0. 2. Все вершины не выделены. 3. Первая вершина объявляется текущей. 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с невыделенной. 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход...
