Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Задача про часовую и минутную стрелки на циферблате http://www.cyberforum.ru/cpp-beginners/thread535745.html
Помогите пожалуйста решить следующую задачу: Даны целые m, n (0<m<=12, 0<=n<60), указывающие момент времени: "m часов, n минут". Определить наименьшее время (число полных минут), которое должно...
C++ Найти значение выражения Найти значение выражения (2*5!+3*8!)/(6!+4!) , определив функцию расчета факториала натурального числа. http://www.cyberforum.ru/cpp-beginners/thread535734.html
Построить программу подсчета количества чисел в массиве, повторяющихся более одного раза C++
Задан положительный массив А Построить программу подсчета количества чисел в этом массиве повторяющихся более одного раза . Например массив 4,5,6,4,9,1,5. одинаковых чисел 2(4,5). Добавлено через...
C++ Как создать тип данных указатель в собственном языке программирования?
/*************************************************************/ /* Компилятоp С0 Д.Г. Хохлов 10.04.03 */ /* */ /* ...
C++ Какой диапазон у переменных типа double ? http://www.cyberforum.ru/cpp-beginners/thread535697.html
В учебнике написано: double _____ 8 байтов _____ от 2.2e-308 до 1.8e308 Насколько я понимаю, строчка от 2.2e-308 до 1.8e308 означает: от 2,2*10-308 до 1,8*10308 то есть числа типа double должны...
C++ Составить программу для вычисления значений функции F(x) Составить программу для вычисления значений функции f (x) на отрезке с шагом h a = -5, \, b = 5, \, h=0,5 f(x)=7 \sin^2 x -\frac 1 2 \cos x Помогите Решить пожалуйста в цикле с предусловием... подробнее

Показать сообщение отдельно
Betokuha
32 / 29 / 9
Регистрация: 05.03.2012
Сообщений: 114

Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда. - C++

01.04.2012, 11:52. Просмотров 1026. Ответов 1
Метки (Все метки)

Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда.

А л г о р и т м Ф л о й д а
Данные: матрица весов С(D) орграфа D.
Результат: расстояния между всеми парами вершин D[i,j] = d(vi,vj).

1. Для всех i = 1,…,n , j = 1,…,n положим D[i,j] = cij .
2. Для всех i = 1,…,n положим D[i,i] = 0.
3. Положим m = 1.
4. Положим i = 1.
5. Положим j = 1.
6. D[i,j] = min ( D[i,j], D[i,m] + D[m,j] ).
7. Если j < n, то положим j = j + 1 и переходим к шагу 6.
8. Если i < n, то положим i = i + 1 и переходим к шагу 5.
9. Если m < n, то положим m = m + 1 и перейдем к шагу 4, иначе алгоритм заканчивает работу. Полученные значения D[i,j] дают расстояния между вершинами vi и vj .

Замечание. Дополнить описанный алгоритм шагами, позволяющими находить сам путь от вершины vi до вершины vj.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru