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

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

Войти
Регистрация
Восстановить пароль
 
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
#1

Нахождения кратчайших путей между всеми парами вершин графа - C++

08.01.2014, 18:12. Просмотров 819. Ответов 9
Метки нет (Все метки)

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

Добавлено через 1 час 45 минут
C++
1
2
3
4
5
for (int k=0; k<n; ++k)
    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j)
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
Вот я что-то нашел. Но не могу в этом коде разобраться.
Источник кода: http://e-maxx.ru/algo/floyd_warshall_algorithm
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2014, 18:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нахождения кратчайших путей между всеми парами вершин графа (C++):

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

Поиск кратчайших путей между двумя вершинами графа методом Шимбела. - C++
Доброго всем время суток!! В универе задали на РГР написать программу в С++, которая находит кратчайший путь между двумя вершинами графа,...

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

Найти диаметр графа, то есть, максимальное значение среди всех кратчайших расстояний между каждой парой вершин - C++
Найти диаметр графа, то есть максимальное значение среди всех кратчайших расстояний между каждой парой вершин. Ответ: номера двух вершин...

Посчитать длины кратчайших путей ориентированного графа - C++
есть задача : задача №138 Алгоритм Форда-Беллмана (Время: 1 сек. Память: 16 Мб Сложность: 38%) Дан ориентированный граф, в котором...

Поиск кратчайших путей из одного источника для неориентированного графа - C++
Дорогие программисты! Прошу вас помочь мне в очень срочном деле! Очень нужен код программы, которая в заголовке на С++. Нашла целую...

9
Kastaneda
Jesus loves me
Эксперт С++
4689 / 2893 / 236
Регистрация: 12.12.2009
Сообщений: 7,357
Записей в блоге: 2
Завершенные тесты: 1
08.01.2014, 18:15 #2
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
если длина некоторых векторов равно 0 (то есть отсутствую).
изначально туда, где 0 пишется INF, потом отсутствующее ребро не проверяется благодаря
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
C++
1
if (d[i][k] < INF && d[k][j] < INF)
0
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
08.01.2014, 18:17  [ТС] #3
Цитата Сообщение от Kastaneda Посмотреть сообщение
изначально туда, где 0 пишется INF, потом отсутствующее ребро не проверяется благодаря
А что такое INF
0
Kastaneda
Jesus loves me
Эксперт С++
4689 / 2893 / 236
Регистрация: 12.12.2009
Сообщений: 7,357
Записей в блоге: 2
Завершенные тесты: 1
08.01.2014, 18:17 #4
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
там же написано
Предполагается, что если между двумя какими-то вершинами нет ребра, то в матрице смежности было записано какое-то большое число (достаточно большое, чтобы оно было больше длины любого пути в этом графе); тогда это ребро всегда будет невыгодно брать, и алгоритм сработает правильно.
Добавлено через 32 секунды
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
А что такое INF
заранее большое число, сделай его равным INT_MAX
0
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
08.01.2014, 18:23  [ТС] #5
То есть чтобы алгоритм верно работал нужно заменить нули на INT_MAX?
0
Kastaneda
Jesus loves me
Эксперт С++
4689 / 2893 / 236
Регистрация: 12.12.2009
Сообщений: 7,357
Записей в блоге: 2
Завершенные тесты: 1
08.01.2014, 18:28 #6
да, если замена будет в оригинальной матрице, то потом не забыть обратно поменять.
0
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
08.01.2014, 18:37  [ТС] #7
Вот код программы:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
using namespace std;
 
int main (void){
    freopen("i.txt", "r", stdin);
    int a[5][5], n=5, i=0, z;
    for(; i<n; i++) for(z=0; z<n; z++) cin >> a[i][z];
 
    for(i=0; i<n; i++) for(z=0; z<n; z++) if(a[i][z]==0 && i!=z) a[i][z]=200000;
 
    for (int k=0; k<n; ++k)
        for (int i=0; i<n; ++i)
            for (int j=0; j<n; ++j){
                 if (a[i][k] < 200000 && a[k][j] < 200000) 
                     a[i][j] = min (a[i][j], a[i][k] + a[k][j]);
            }
 
    for(i=0; i<n; i++){
        for(z=0; z<n; z++) cout << a[i][z] << " ";
        cout << "\n";
    }
}
При тесте:
0 1 0 0 0
0 0 3 0 100
0 3 0 3 5
0 0 3 0 3
0 100 5 3 0


Видает ответ:
0 1 4 7 9
200000 0 3 6 8
200000 3 0 3 5
200000 6 3 0 3
200000 8 5 3 0


А нужно:
0 1 4 7 9
1 0 3 6 8
4 3 0 3 5
7 6 3 0 3
9 8 5 3 0
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.01.2014, 18:59 #8
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
C++
1
a[i][j] = min (a[i][j], a[i][k] + a[k][j]);
попробуйте заменить на:
C++
1
a[j][i]=a[i][j] = min (a[i][j], a[i][k] + a[k][j]);
1
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
08.01.2014, 19:12 #9
можно попробывать вместо Флойда-Уоршелла запустить Дейкстру на куче N раз, по асимптотике вроде выигрывает, но скрытая константа у Дейкстры по-больше будет
0
some_name
Вежливость-главное оружие
226 / 224 / 55
Регистрация: 19.02.2013
Сообщений: 1,441
08.01.2014, 19:14 #10
Попробуйте применить метод обхода в ширину. Вот здесь есть рабочий код.
0
08.01.2014, 19:14
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.01.2014, 19:14
Привет! Вот еще темы с ответами:

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

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

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

Алгоритм для поиска всех путей между 2 вершинами графа - C++
Здравствуйте, возник вопрос какой алгоритм необходимо использовать для поиска всех путей, между 2 вершинами графа.


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

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

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