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

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

Восстановить пароль Регистрация
 
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
08.01.2014, 18:12     Нахождения кратчайших путей между всеми парами вершин графа #1
Подскажите как можно улучшить алгоритм Флойда-Уоршелла что-бы он верно работал если длина некоторых векторов равно 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2014, 18:12     Нахождения кратчайших путей между всеми парами вершин графа
Посмотрите здесь:

C++ Поиск кратчайших путей из одного источника для неориентированного графа
C++ Поиск кратчайших путей между двумя вершинами графа методом Шимбела.
Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда. C++
Задачка со строками(Требуется вставить символ между всеми парами соседних символов в строке) C++
C++ Прогрмма по поиску кратчайших путей в графе
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
08.01.2014, 18:15     Нахождения кратчайших путей между всеми парами вершин графа #2
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
если длина некоторых векторов равно 0 (то есть отсутствую).
изначально туда, где 0 пишется INF, потом отсутствующее ребро не проверяется благодаря
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
C++
1
if (d[i][k] < INF && d[k][j] < INF)
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
08.01.2014, 18:17  [ТС]     Нахождения кратчайших путей между всеми парами вершин графа #3
Цитата Сообщение от Kastaneda Посмотреть сообщение
изначально туда, где 0 пишется INF, потом отсутствующее ребро не проверяется благодаря
А что такое INF
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
08.01.2014, 18:17     Нахождения кратчайших путей между всеми парами вершин графа #4
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
там же написано
Предполагается, что если между двумя какими-то вершинами нет ребра, то в матрице смежности было записано какое-то большое число (достаточно большое, чтобы оно было больше длины любого пути в этом графе); тогда это ребро всегда будет невыгодно брать, и алгоритм сработает правильно.
Добавлено через 32 секунды
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
А что такое INF
заранее большое число, сделай его равным INT_MAX
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
08.01.2014, 18:23  [ТС]     Нахождения кратчайших путей между всеми парами вершин графа #5
То есть чтобы алгоритм верно работал нужно заменить нули на INT_MAX?
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
08.01.2014, 18:28     Нахождения кратчайших путей между всеми парами вершин графа #6
да, если замена будет в оригинальной матрице, то потом не забыть обратно поменять.
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
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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]);
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
08.01.2014, 19:12     Нахождения кратчайших путей между всеми парами вершин графа #9
можно попробывать вместо Флойда-Уоршелла запустить Дейкстру на куче N раз, по асимптотике вроде выигрывает, но скрытая константа у Дейкстры по-больше будет
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.01.2014, 19:14     Нахождения кратчайших путей между всеми парами вершин графа
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
some_name
Вежливость-главное оружие
 Аватар для some_name
219 / 219 / 55
Регистрация: 19.02.2013
Сообщений: 1,419
08.01.2014, 19:14     Нахождения кратчайших путей между всеми парами вершин графа #10
Попробуйте применить метод обхода в ширину. Вот здесь есть рабочий код.
Yandex
Объявления
08.01.2014, 19:14     Нахождения кратчайших путей между всеми парами вершин графа
Ответ Создать тему
Опции темы

Текущее время: 23:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru