Графы |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Графы |
Van |
Сообщение
#1
|
Гость |
Здравствуйте. Есть такая проблема. Дана задача, где надо реализовать
алг. Дейкстры(кратчайшее раст. от одной до всех вершин) для графов. Алг. я знаю, но нужна матрица смежностей, которой нет в условии. пример: 5 3 1 (5 — n вершин 3-число краев(не знаю зачем) 1-стартовая вершина)) 1 2 5 (1 соединена с 2 5-весс ребра) 1 3 7 (1 соединена с 3 7-весс ребра) 3 4 10(---) Ответ: 0 5 7 17 -1 Есть ли алгоритм где не нужна мат. см.? или Как составить её по этим данным? 5 3 1 1 2 5 1 3 7 …….. Это не совсем мат. см.( по моему мнению) а вот это, да 0 1 6 3 3 0 5 3 5 6 0 4 1 6 8 0 Если заполнять по первому примеру то -> 0 5 7 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 (я так делал, на выходе одни нули т.к мат. плохо заполнена) Так вот эту ерунду надо достроить до нормальной матрицы, с реальными данными. Но вот как? по-моему данных просто мало. Или надо реализовать хитрый проход по матрице? 0 5 7 17 -1 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 а потом по a[1, j] выводить? Но тогда зачем алг. Дейкстры? помогите пожалуйста. |
volvo |
Сообщение
#2
|
Гость |
Цитата(Van @ 26.10.2005 11:37) по-моему данных просто мало. По моему, тоже... У тебя 5 вершин, и только 2 (или 3) связи между ними? Данных явно недостаточно. Как только будут ВСЕ связи между вершинами, можно будет составить матрицу смежности... |
Altair |
Сообщение
#3
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
http://forum.pascal.net.ru/index.php?showt...indpost&p=42335
Это алгоритм. для твоего графа: Цитата 5 3 1 1 2 5 1 3 7 3 4 10 Матрица смежности имеет вид: С ней запросто справляется алгоритм Дейкстры который по ссылке... вот и все. p.s. правда конткретный граф глупый, смысла искать кратчайшие пути нет... -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Guest |
Сообщение
#4
|
Гость |
Спасибо всем тем, кто ответил мне, каждое ваше слово наводило на меня правильные мысли. Алгоритм Дейкстры я реализовал ещё 2 надели назад, пришлось спросить у препода одно, реализовать чуток другое, в общем главная ошибка - я для решения делал матрицу симметричной ->
Цитата 0 1 2 3 1 0 2 0 3 for I := 1 to levChis do А надо было просто тупо её заполнять -> Read(f1, n, levChis, start); { levChis - число граней start - стартовая вершина} Т.е граф был ориентированный. Вот после этого у меня всё правильно сработало (см. ниже) . А теперь мне надо реализовать алг. BFS(Breadth-first-search (поиск в ширину)), И ещё Флойда. Подскажите пожалуйста где мне найти инфу по этому, да и вообще по графам. А то у меня материала очень мало. (Компилил на Дельфи) program Deijckstra; Сообщение отредактировано: volvo - |
Altair |
Сообщение
#5
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
-------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Текстовая версия | 2.06.2024 17:16 |