|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
16.11.2010, 20:03 | #1 |
Регистрация: 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, хотя все остальные считает верно) |
16.11.2010, 20:35 | #2 |
Great Code Monkey
Форумчанин
Регистрация: 09.08.2007
Сообщений: 533
|
Все правильно - вершина 6 недостижима из вершины 3, если граф ориентированный. Показывай матрицу смежности.
|
17.11.2010, 00:21 | #3 |
Регистрация: 16.11.2010
Сообщений: 7
|
Все, понял. Извините)
Я пропустил что Ф-У работает только для строго ориентированного. Нужно чтоб для любого. Буду думать как менять обход или писать тогда Дейскриту. |
17.11.2010, 00:35 | #4 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
По сути, неориентированный можно представить, как ориентированный, в котором на месте ребер противоположно направленные пары дуг. Т.е. просто надо, чтоб в матрице для неора было m[i][j]==m[j][i], при считывании ребра отмечать его в оба направления, и тогда получним норм.
|
17.11.2010, 11:36 | #5 |
Регистрация: 16.11.2010
Сообщений: 7
|
LeBron > Спасибо большое! Теперь все работает
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм Флойда. Поиск Кратчайшего пути. | 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 |