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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.81
From_Tula
40 / 40 / 2
Регистрация: 22.05.2009
Сообщений: 483
#1

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

25.05.2010, 20:38. Просмотров 4718. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Дейкстры (C++):

Алгоритм Дейкстры - C++
Ребятушки, помогите, пожалуйста. Нужна реализация алгоритма дейкстры на паскале, а именно вот этого кода const int INF = 1000000000; ...

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

Алгоритм Дейкстры - C++
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность...

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

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

Алгоритм Дейкстры - C++
Написал программу, проверил код, в MVS6 С++ компилируется без ошибок. Но вот не задача, программа рушиться(не выполняется) при количестве...

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

Алгоритм Дейкстры - C++
Как на С++ в консольном приложении описать алгоритм Дейкстры?

Алгоритм Дейкстры - C++
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а дальше-нет. #include<iostream> #include<fstream> ...

Алгоритм Дейкстры - C++
День добрый! Есть игровое поле M*M. Количесво графов - N. Есть матрица смежности этого игрового поля. Получить элемент матрицы можно...

Рекурсивный алгоритм Дейкстры - C++
Добрый день, необходима помощь в алгоритме trains - матрица, сохраняющая длины ребер stations - количество графов start - граф, с...


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

Или воспользуйтесь поиском по форуму:
4
Yandex
Объявления
26.06.2011, 00:05
Ответ Создать тему
Опции темы

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