Составить программу по алгоритму Дейкстры определения оптимальных маршрутов от исходной до всех остальных вершин графа.
Вход: матрица нагрузок на ребра графа, номер исходной вершины;
Выход: последовательность вершин, проходимых по оптимальному пути до каждой вершины, длина каждого из оптимальных маршрутов.
Описание метода:
Программа реализует алгоритм Дейкстры для нахождения кратчайшего пути от заданной начальной вершины до всех остальных вершин в графе. Алгоритм основан на приписывании вершинам временных пометок, которые являются верхними границами длины пути от начальной вершины до этой вершины. Пометки постепенно уменьшаются на каждом шаге итерации, и на каждом шаге итерации точно одна из пометок становится постоянной, что означает, что эта пометка уже не является верхней границей, а дает точную длину кратчайшего пути от начальной вершины до рассматриваемой вершины.
Подключаемые библиотеки:
iost...