|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
04.06.2009, 14:03 | #1 |
Пользователь
Регистрация: 27.05.2008
Сообщений: 14
|
Алгоритм Дейкстры поиска путей в графе. Как реализовать с помощью приоритетной очереди?
Вот задача: найти радиус графа с помощью алгоритма Дейкстры. Как работает алгоритм я знаю. Единственная проблема - надо реализовать его с использованием приритетной очереди (двоичной кучи, пирамиды, что почти одно и то же).
Приоритетная очередь у меня есть. Я могу загнать в неё все вершины и доставать ту, у которой метка меньше всех. Только вот проблема: надо в процессе обхода смежных вершин осуществлять так называемые релаксации, которые уменьшают метку вершин. Естественно, изменение меток должно отражаться и в очереди, только я не нашёл способа это сделать. Я даже могу изменять конкретный элемент очереди, по индексу в ней, только индекс неизвестен, потому что элементы в процессе извлечения и изменения перемешиваются. Если кто-то хочет ознакомиться с алгоритмом дейкстры, то вот ссылка: http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
применить Алгоритм Дейкстры для поиска кратчайшего пути в графе | Эдгар | Microsoft Office Excel | 13 | 24.10.2008 21:01 |
Помогите! Как реализовать перемещение панель GroupControl с помощью мыши. | Slavon | Общие вопросы .NET | 0 | 14.05.2008 13:49 |
Алгоритм Дейкстры | Dimon88 | Помощь студентам | 2 | 03.11.2007 17:13 |
как на асме реализовать алгоритм манчестерского кодирования | Lanches | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 0 | 17.07.2007 13:50 |