Применение алгоритма Флойда для решения задачи о кратчайшем пути

1. Применение алгоритма Флойда для решения задачи о кратчайшем пути

Я
Л
Д У ТИ
А П
Д
Й М
О
Е
Л
Ш
Ф
А АЙ
М ТЧ
Т
И РА
Р
О К
Г
О
Л
А ЧИ
Е
И ДА
Н
Е ЗА
Н
Е Я
М
И
Н
И
ПР ШЕ
РЕ

2.

Актуальность
задачи о
кратчайшем пути

3.

Кратчайший путь (A, C, E, D, F) между вершинами
A и F во взвешенном ориентированном графе.

4. Алгоритмы нахождения кратчайшего пути

АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШЕГО
ПУТИ
1) Алгоритм Форда-Беллмана
2) Алгоритм Дейкстры
3) Алгоритм Флойда

5. Роберт флойд 8.06.1936 – 25.09.2001

РОБЕРТ
ФЛОЙД
8.06.1936
–
25.09.2001

6.

for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (array[i, j] > array[i, k] + array[k, j])
array[i, j] = array[i, k] + array[k, j];

7. Программная реализация

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

8.

9. Заключение

ЗАКЛЮЧЕНИЕ
1)Освоение алгоритма и его реализация
2)Осуществление отрисовки графа
возможно улучшение алгоритма для
применения на практике
Выполнил студент 3 курса, 61 группы
Бельков Дмитрий