Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 16.11.2010, 20:03   #1
_Disa
 
Регистрация: 16.11.2010
Сообщений: 7
По умолчанию Алгоритм Флойда-Уоршела

День добрый. Написал алгоритм Флойда-Уоршела. Вот код:

void F_U( int m[][], int n) {
for ( k = 0; k < n; k++ )
for ( i = 0; i < n; i++ )
for ( j = 0; j < n; j++ ) {
if ( m[i][j] > ( m[i][k] + m[k][j] ) )
m[i][j] = m[i][k] + m[k][j];
}

матрица смежности инициализирована как нужно( по диагонали нули, отсутствующие ребра +INF, а где нужно положительные величины). Почему-то на следующем графе не правильно считает расстояние от 3 до 6ой вершин:
1 - > 2 dist: 7
2 - > 3 dist: 3
2 - > 4 dist: 6
4 - > 5 dist: 3
5 - > 6 dist: 1

Выдает что 3 -> 6 min_dist: INF никак не могу понять почему так, уже часа 3и гонял дебагером по циклу((
причем все похожие расстояния( то есть 6 в 4 или 6 в 5 тоже считает как INF, хотя все остальные считает верно)
_Disa вне форума Ответить с цитированием
Старый 16.11.2010, 20:35   #2
still_alive
Great Code Monkey
Форумчанин
 
Аватар для still_alive
 
Регистрация: 09.08.2007
Сообщений: 533
По умолчанию

Все правильно - вершина 6 недостижима из вершины 3, если граф ориентированный. Показывай матрицу смежности.
still_alive вне форума Ответить с цитированием
Старый 17.11.2010, 00:21   #3
_Disa
 
Регистрация: 16.11.2010
Сообщений: 7
По умолчанию

Все, понял. Извините)
Я пропустил что Ф-У работает только для строго ориентированного. Нужно чтоб для любого. Буду думать как менять обход или писать тогда Дейскриту.
_Disa вне форума Ответить с цитированием
Старый 17.11.2010, 00:35   #4
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

По сути, неориентированный можно представить, как ориентированный, в котором на месте ребер противоположно направленные пары дуг. Т.е. просто надо, чтоб в матрице для неора было m[i][j]==m[j][i], при считывании ребра отмечать его в оба направления, и тогда получним норм.
LeBron вне форума Ответить с цитированием
Старый 17.11.2010, 11:36   #5
_Disa
 
Регистрация: 16.11.2010
Сообщений: 7
По умолчанию

LeBron > Спасибо большое! Теперь все работает
_Disa вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм Флойда. Поиск Кратчайшего пути. Shady Помощь студентам 5 06.10.2014 18:29
Алгоритм Флойда Александр36М Помощь студентам 5 14.10.2011 16:16
Алгоритм Флойда Дим@@ Помощь студентам 4 25.10.2010 20:19
Волновой алгоритм (алгоритм Ли) MrRockchip Общие вопросы C/C++ 4 10.05.2010 13:26