Программная реализация алгоритма Беллмана-Форда
После ввода всех необходимых данных программа высчитывает кратчайшие пути от исследуемой вершины орграфа до всех остальных его вершин. На рисунке 10 представлен результат работы программы. Проверим работу программы используя для исследования орграф с наличием дуг отрицательного веса (см. рисунок 12). На рисунке 11 представлен результат работы программы с тем же графом, но для вершины под номером… Читать ещё >
Программная реализация алгоритма Беллмана-Форда (реферат, курсовая, диплом, контрольная)
В результате проделанной работы была разработана и реализована программа поиска кратчайших путей от заданной вершины до всех остальных вершин данного ориентированного графа с помощью алгоритма Беллмана-Форда. Программа написана на языке C++ в среде Microsoft Visual C++ 2010. Код программы приведен в приложении А.
При запуске программы появляется окно, представленное на рисунке 8.
Рисунок 8 — Запуск программы.
Пользователю необходимо ввести в появившемся окне количество вершин исследуемого орграфа, количество дуг и информацию о весе каждой дуги. Для демонстрации работы программы будем использовать данные орграфа, представленного на рисунке 9. В качестве исследуемой вершины выберем вершину 1.
Рисунок 9 — Ориентированный граф.
После ввода всех необходимых данных программа высчитывает кратчайшие пути от исследуемой вершины орграфа до всех остальных его вершин. На рисунке 10 представлен результат работы программы.
Рисунок 10 — Результат работы программы.
На рисунке 11 представлен результат работы программы с тем же графом, но для вершины под номером 2.
Рисунок 11 — Результат работы программы.
Проверим работу программы используя для исследования орграф с наличием дуг отрицательного веса (см. рисунок 12).
Рисунок 12 — Орграф с дугами отрицательного веса.
Результат работы программы представлен на рисунке 13.
Рисунок 13 — Результат работы программы.