|
Вернуться на страницу "Банк студенческих задач"
 Архив разработки (32 Кб, Mathcad-документ)
Содержание
1. Задание матрицы весов ориентированного графа
2. Реализация алгоритма Дейкстры и применение его к заданному графу
Задание матрицы весов ориентированного графа
 - количество вершин графа
Элемент Si,j равен весу ребра, соединяющего i-ую и j-ую вершины. Для бесконечности используется число "1000". Его можно задавать в зависимости от конкретной задачи. Оно означает, что пути из вершины i в вершину j не существует. Веса в матрице не должны быть отрицательными.
Реализация алгоритма Дейкстры и применение его к заданному графу
|
|
Все вершины не отмечены
помечаем начальную вершину
Бесконечный цикл
Hаходим минимум среди неотмеченных вершин
Запоминаем растояние до этой вершины и ее номер.
Выход, если дошли до конечной вершины.
|
На выходе из функции Func1() получаем матрицу, первая колонка которой представляет вектор растояний от заданной вершины до остальных; из второй колонки можновыразить путь от конечной до начальной вершины с помощью функции Func2().
|
|
Выделяем вторую колонку
из матрицы С
Бесконечный цикл
Начинаем выделять путь из конечной вершины
Выход, если доходим до начальной вершины
Переписываем путь в прямом порядке
|
|
|
Задаем начальную и конечную вершины
|
|
Путь из вершины v_n в вершину v_k:
Расстояние между вершинами v_n и v_k:
|
|
Вывод: Алгоритм Дейкстры является одним из самых быстрых для поиска кратчайших расстояний от некоторой вершины до всех остальных. Он имеет сложность w2.
Вернуться на страницу "Банк студенческих задач"
|
