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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Betokuha
32 / 29 / 9
Регистрация: 05.03.2012
Сообщений: 114
#1

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

01.04.2012, 11:52. Просмотров 998. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.04.2012, 11:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда. (C++):

Нахождения кратчайших путей между всеми парами вершин графа - C++
Подскажите как можно улучшить алгоритм Флойда-Уоршелла что-бы он верно работал если длина некоторых векторов равно 0 (то есть отсутствую). ...

Вычислить количество различных путей между всеми парами вершин графа - C++
Задан граф с N вершинами вычислить количество различных путей между всеми парами вершин графа

Исключить из текста символы, расположенные между всеми парами скобок - C++
Задание: Дан текст. Исключить из него символы, расположенные между всеми парами скобок (, ). Сами скобки тоже должны быть исключены....

Задачка со строками(Требуется вставить символ между всеми парами соседних символов в строке) - C++
Здравствуйте! Есть такая задачка:Файл состоит из записей вида &quot;s пробел c&quot;, где s -строка, а с - символ. Требуется вставить с между всеми...

В одномерном массиве из целых чисел вставить новый элемент между всеми парами элементов, имеющими разные знаки - C++
одномерном массиве из целых чисел вставить новый элемент между всеми парами элементов,имеющими разные знаки

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе - C++
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска кратчайшего пути между двумя...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Betokuha
32 / 29 / 9
Регистрация: 05.03.2012
Сообщений: 114
15.05.2012, 18:23  [ТС] #2
Дайте совети
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.05.2012, 18:23
Привет! Вот еще темы с ответами:

Восстановление пути по матрице, возвращаемой алгоритмом Флойда - Уоршелла - C++
Делаю, алгоритм флойда-уоршелла, делаю сам на делфи, но исходники с решением моей проблемы (ну по крайней мере я надеюсь, что с решением)...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Алгоритм Флойда Оршала - C++
Найти наикратчайшее расстояние от каждой до каждой. Задание представляет собой любую матрицу 4*4. Программа на языке C++.

Алгоритм Флойда-Уоршела - C++
Ребят, помогите. На завтра нужно сдать алгоритм флойда. Вроде нашел код, но он не выводит САМО ЗНАЧЕНИЕ кратчайшего пути, а только по каким...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru