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

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

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

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

25.05.2010, 20:38. Просмотров 4667. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2010, 20:38     Алгоритм Дейкстры
Посмотрите здесь:

Алгоритм Дейкстры (цена на бензин) - C++
Думаю с этой задачей многие сталкивались :) Входные данные Во входном файле INPUT.TXT записано сначала число N (1 ≤ N ≤ 100), затем...

Работа с графами. Алгоритм Дейкстры - C++
Может у кого есть исходник для реализации алгоритма Дейкстры, когда граф представлен не матрицей смежности, а списком рёбёр. Просто есть...

Вставить алгоритм Дейкстры в программу - C++
Вот рабочая программа которая находит кратчайшый путь по алгоритму Дейкстры А вот моя в которую нужно вставить алгоритм ...

Вывод пути (алгоритм Дейкстры) - C++
Реализация алгоритма Дейкстра. В массиве distance - найденные кратчайшие пути, visited - логический, для хранения информации о...

Алгоритм Дейкстры с рандомной матрицей - C++
Необходимо, чтобы при запуске программы создавалась рандомная матрица 9x9 в которой: рандом генерируется по всей матрице, кроме главной...

Алгоритм Дейкстры. Консольное приложение - C++
Помогите, помогите, помогите кто чем может, пожалуйста!.. срочно пипец вообще как нужна программа на плюсах, реализующая алгоритм Дейкстры...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2011, 00:05     Алгоритм Дейкстры
Еще ссылки по теме:

Алгоритм Дейкстры для лабиринта - C++
Лабиринт задается матрицей, где 0 стены, 1 проходы, s - начальная вершина, f - конечная. Лабиринт считывается из файла. Не могу сообразить,...

Алгоритм Дейкстры неправильно выводит путь - C++
вот прога, но она неправильно выводит путь((( #include<iostream> #include<fstream> #include<conio.h> #include<locale.h> ...

Алгоритм Дейкстры в связном списке + файлы. - C++
Задача такова : Имеются n городов. Некоторые из них соединены дорогами известной длины. Найти кратчайшие маршруты из заданного города в...

Алгоритм Дейкстры (часть кода есть) - C++
Здравствуйте! Нужно реализовать на С++ такую консольную программу: 1. Задается массив размерности n; 2. Найти максим. j такой, что a...

Требуется реализовать алгоритм Дейкстры начинающему программисту - C++
Ребята огромная просьба помочь с программой. Условия следушие-реализовать алгоритм Дейкстры на С++. Я сидел парился и смог только часть...

Задача на алгоритм Дейкстры (как лучше хранить информацию?) - C++
Доброго времени суток. Есть задача: Есть идея хранить входные данные след. образом: Выделить в памяти 2-х матрицы(Tab1 и Tab2...


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

Или воспользуйтесь поиском по форуму:
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
26.06.2011, 00:05     Алгоритм Дейкстры #4
то что вы пишете - матрицы весов (стоимостей)
а смежности - из 0 и 1, показывают смежны ли вершины
странные вы люди
Yandex
Объявления
26.06.2011, 00:05     Алгоритм Дейкстры
Ответ Создать тему
Опции темы

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