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

Алгоритм Дейкстры - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.81
From_Tula
40 / 40 / 2
Регистрация: 22.05.2009
Сообщений: 469
25.05.2010, 20:38     Алгоритм Дейкстры #1
Пытаюсь сейчас его понять, как я понял сперва надо оставить матрицу смежности, и все возможные связи между вершинами заполнить их длинами, а если связи нет, то ставим 0.

Вот я попробывал составить матрицу смежности для данного графа.
Так она должна выглядить или нет?
Алгоритм Дейкстры

0 7 9 0 0 14
7 0 10 15 0 0
9 10 0 11 0 2
0 15 11 0 6 0
0 0 0 6 0 9
14 0 2 0 9 0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2010, 20:38     Алгоритм Дейкстры
Посмотрите здесь:

Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры С++ C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Adler
 Аватар для Adler
78 / 78 / 3
Регистрация: 07.05.2009
Сообщений: 316
25.05.2010, 21:20     Алгоритм Дейкстры #2
Цитата Сообщение от From_Tula
Так она должна выглядить или нет?
похоже что так.
Sept
Сообщений: n/a
30.05.2010, 16:05     Алгоритм Дейкстры #3
Вообще говоря, при составлении матриц смежности 0 ставится в случае, если Vi=Vj и у вершины нет петли. Если же от одной вершины прямого пути до другой нет, то ставится либо бесконечность, либо очень большое число (100 или 1000, главное, чтобы больше суммы весов всех ребер). Иначе, если поставить 0, то получается, что длина пути из одной вершины до другой есть 0, т е это одна и та же вершина, что при несовпадении Vi и Vj неверно, и алгоритм Дейкстры неверен.
В вашем случае, матрица смежности для данного графа будет выглядеть следующим образом:
0 7 9 100 100 14
7 0 10 15 100 100
9 10 0 11 100 2
100 15 11 0 6 100
100 100 100 6 0 9
14 100 2 100 9 0
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
26.06.2011, 00:05     Алгоритм Дейкстры #4
то что вы пишете - матрицы весов (стоимостей)
а смежности - из 0 и 1, показывают смежны ли вершины
странные вы люди
Yandex
Объявления
26.06.2011, 00:05     Алгоритм Дейкстры
Ответ Создать тему
Опции темы

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