Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/28: Рейтинг темы: голосов - 28, средняя оценка - 4.64
From_Tula
40 / 40 / 10
Регистрация: 22.05.2009
Сообщений: 487
1

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

25.05.2010, 20:38. Просмотров 5056. Ответов 3
Метки нет (Все метки)

Пытаюсь сейчас его понять, как я понял сперва надо оставить матрицу смежности, и все возможные связи между вершинами заполнить их длинами, а если связи нет, то ставим 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2010, 20:38
Ответы с готовыми решениями:

Алгоритм Дейкстры
Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной...

Алгоритм Дейкстры
Всем доброго дня! Столкнулся с проблемой, никак не могу понять, как лучше...

Алгоритм Дейкстры
Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 1.5...

Алгоритм Дейкстры
Всем добрый день,уважаемые программисты! Помогите пожалуйста решить вот эту...

Алгоритм Дейкстры
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а...

3
Adler
79 / 79 / 19
Регистрация: 07.05.2009
Сообщений: 316
25.05.2010, 21:20 2
Цитата Сообщение от From_Tula
Так она должна выглядить или нет?
похоже что так.
1
Sept
0 / 0 / 0
Регистрация: 27.05.2010
Сообщений: 2
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
0
Healius
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
26.06.2011, 00:05 4
то что вы пишете - матрицы весов (стоимостей)
а смежности - из 0 и 1, показывают смежны ли вершины
странные вы люди
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2011, 00:05

Алгоритм Дейкстры С++
Реализовать алгоритм поиска кратчайшего пути. Алгоритм Дейкстры. Представление...

Алгоритм Дейкстры
Здравствуйте!!! Есть код для нахождения длин от начальной вершины до всех...

Алгоритм Дейкстры
Ребятушки, помогите, пожалуйста. Нужна реализация алгоритма дейкстры на...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru