10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
1

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

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

Author24 — интернет-сервис помощи студентам
Подскажите как можно улучшить алгоритм Флойда-Уоршелла что-бы он верно работал если длина некоторых векторов равно 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.01.2014, 18:12
Ответы с готовыми решениями:

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

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

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

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

9
5232 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,143
Записей в блоге: 2
08.01.2014, 18:15 2
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
если длина некоторых векторов равно 0 (то есть отсутствую).
изначально туда, где 0 пишется INF, потом отсутствующее ребро не проверяется благодаря
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
C++
1
if (d[i][k] < INF && d[k][j] < INF)
0
10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
08.01.2014, 18:17  [ТС] 3
Цитата Сообщение от Kastaneda Посмотреть сообщение
изначально туда, где 0 пишется INF, потом отсутствующее ребро не проверяется благодаря
А что такое INF
0
5232 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,143
Записей в блоге: 2
08.01.2014, 18:17 4
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
там же написано
Предполагается, что если между двумя какими-то вершинами нет ребра, то в матрице смежности было записано какое-то большое число (достаточно большое, чтобы оно было больше длины любого пути в этом графе); тогда это ребро всегда будет невыгодно брать, и алгоритм сработает правильно.
Добавлено через 32 секунды
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
А что такое INF
заранее большое число, сделай его равным INT_MAX
0
10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
08.01.2014, 18:23  [ТС] 5
То есть чтобы алгоритм верно работал нужно заменить нули на INT_MAX?
0
5232 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,143
Записей в блоге: 2
08.01.2014, 18:28 6
да, если замена будет в оригинальной матрице, то потом не забыть обратно поменять.
0
10 / 10 / 1
Регистрация: 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
Эксперт С++
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
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
Мой лучший друг-отладчик!
167 / 167 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
08.01.2014, 19:12 9
можно попробывать вместо Флойда-Уоршелла запустить Дейкстру на куче N раз, по асимптотике вроде выигрывает, но скрытая константа у Дейкстры по-больше будет
0
Вежливость-главное оружие
233 / 234 / 86
Регистрация: 19.02.2013
Сообщений: 1,446
08.01.2014, 19:14 10
Попробуйте применить метод обхода в ширину. Вот здесь есть рабочий код.
0
08.01.2014, 19:14
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.01.2014, 19:14
Помогаю со студенческими работами здесь

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

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru