проходить найкоротший шлях. При цьому початкова та кінцева точка також відображаються в цьому стовпці.
ПРИКЛАД ВИКОРИСТАННЯ ПРОГРАМНОЇ РЕАЛІЗАЦІЇ
Нехай є орієнтований зважений граф на п'яти вершинах. Його матриця суміжності має вигляд:
Таблиця 1. Матриця суміжності.
вершина123451010030902005000300001540020060500000
Необхідно знайти найкоротший шлях між вершинами 1 і 5.
. Дана матриця суміжності записується у файл testdata.xls:
Рис. 2. Завдання матриці суміжності.
. У командному вікні Matlab викликається функція deikstra (1, 5), де в якості аргументів указуються відповідні номери початкової та кінцевої вершини:
Рис. 3. Виклик функції, що реалізує алгоритм Дейкстри
. На екран виводиться результат:
Рис. 4. Висновок результату.
ВИСНОВОК
У даній роботі була вивчена тема «Пошук найкоротшого шляху в графі» ??на основі алгоритму Дейкстри. Для вивчення роботи даного алгоритму була написана відповідна програма. Програма реалізована в середовищі Matlab. Працездатність написаної програми була перевірена на тестових прикладах, один з яких наведено в роботі.
Вивчений алгоритм є досить простим у розумінні та програмної реалізації.
Отримані результати узгоджуються з теорією.
ЛІТЕРАТУРА
Стаття в Інтернеті:
