Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/14: Рейтинг темы: голосов - 14, средняя оценка - 4.86
Смирняга
71 / 16 / 2
Регистрация: 29.12.2010
Сообщений: 339
1

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

30.03.2014, 23:34. Просмотров 2711. Ответов 6
Метки нет (Все метки)

Уже больше суток бьюсь над формулированием запроса в гугл, чтобы он мне выдал какой-нибудь мануал по реализации алгоритма Дейкстры на d-куче.
Нужно найти кратчайшие пути до всех узлов от заданного узла. Сам алгоритм Дейкстры уже реализовал. Что такое d-кучи понимаю и могу реализовать без проблем. А вот связать все вместе или найти как это сделать не могу уже долго. Сдавать через 7 часов. Помогите раскурить, пожалуйста

Добавлено через 12 минут
бамп. Никто не знает, чтоли?
нашел только сомнительный код на плюсах
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const int inf = 1e9;
class edge
{
public :
    int v, w;
    edge (int _v, int _w) : v (_v), w (_w) {};
};
bool operator < (edge a, edge b) { return a.w < b.w || (a.w == b.w && a.v < b.v); }
bool operator == (edge a, edge b) { return a.w == b.w && a.v == b.v; }
 
void dij_sparse (int x, vector < vector < edge > > &e, vector < int > &w, vector < int > &p)
{
    int i, j;
    int n = e.size ();
    vector < int > a (n, 0);
    w.assign (n, inf);
    p.assign (n, - 1);
    w[x] = 0;    
    set < edge > u;
    for (i = 0; i < n; ++ i)
        u.insert (edge (i, i == x ? 0 : inf));
    
    for (i = 0; i < n; ++ i)
    {
        int v = (* u.begin ()).v;
        u.erase (u.begin ());
        a[v] = 1;
        
        for (j = 0; j < e[v].size (); ++ j)
        {
            int to = e[v][j].v;
            if (!a[to] && w[to] > w[v] + e[v][j].w)
            {
                u.erase (u.find (edge (to, w[to])));
                w[to] = w[v] + e[v][j].w;
                p[to] = v;
                u.insert (edge (to, w[to]));
            }
        }
    }
}
Взято с http://hardfire.ru/Dij_sparse
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2014, 23:34
Ответы с готовыми решениями:

Сетевые алгоритмы. Найти кратчайшие пути от узла 1 до всех остальных узлов
Найти кратчайшие пути от узла 1 до всех остальных узлов . Описать алгоритм .

Алгоритм Дейкстры на двоичной куче
Добрый вечер! Подскажите, как реализовать Дейкстру на 2-куче? Как пишется куча - знаю, как пишется...

Реализовать алгоритм Дейкстры от первой вершины до всех остальных - найти ошибку
помогите с програмой program Dijkstra; uses crt; const V=6; inf=100000; type vektor=array of...

поиск пути. алгоритм Дейкстры
доброго времени суток) обработка графа реализована через 2 динамических массива и процедуру...

6
Psilon
Master of Orion
Эксперт .NET
6058 / 4916 / 903
Регистрация: 10.07.2011
Сообщений: 14,520
Записей в блоге: 5
Завершенные тесты: 4
30.03.2014, 23:43 2
Смирняга, не знаю при чем тут куча, простейший алгоритм дейкстры вот:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
using System;
using System.Collections.Generic;
 
namespace Dijkstra
{
    class Program
    {
        private static void Main()
        {
 
            const int n = 5;
            var adjacencyMatrix = new int[n, n];
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    adjacencyMatrix[i, j] = -1;
                }
            }
            adjacencyMatrix[0, 1] = 10;
            adjacencyMatrix[0, 3] = 30;
            adjacencyMatrix[0, 4] = 100;
            adjacencyMatrix[1, 2] = 50;
            adjacencyMatrix[2, 0] = 70;
            adjacencyMatrix[2, 4] = 10;
            adjacencyMatrix[3, 2] = 20;
            adjacencyMatrix[4, 3] = 60;
 
            var costs = new int[n];
            for (int i = 1; i < costs.Length; i++)
            {
                costs[i] = int.MaxValue;
            }
 
            for (int i = 0; i < n; i++)
            {
                var list = new List<int>();
                for (int j = i; j < n; j++)
                {
                    if (adjacencyMatrix[i, j] != -1)
                        list.Add(j);
                }
                list.Sort((x, y) => adjacencyMatrix[i, x].CompareTo(adjacencyMatrix[i, y])); //Сортируем по мин. стоимости пути
                foreach (var j in list)
                {
                    var newcost = costs[i] + adjacencyMatrix[i, j];
                    if (newcost < costs[j])
                        costs[j] = newcost;
                }
            }
            for (int i = 0; i < costs.Length; i++)
            {
                Console.WriteLine("Пункт {0}, стоимость пути = {1}", i, costs[i]);
            }
            Console.ReadKey();
        }
    }
}
1
Смирняга
71 / 16 / 2
Регистрация: 29.12.2010
Сообщений: 339
30.03.2014, 23:57  [ТС] 3
Алгоритм Дейкстры, реализованный на основе d-кучи
Представим d-кучу массивом имен name[1..n] и массивом ключей key[1..n] так, что key[i] является текущей оценкой длины кратчайшего пути от вершины s к вершине name[i]. В данном алгоритме (см. [4]), представленном процедурой LDG_DIJKSTRA_D-HEAP, также используется массив index[1..n], который должен поддерживаться так, чтобы index[name[i]]:= i при i=1, …, n. Для достижения этой цели каждая строка “{+}” в псевдокоде операций ВСПЛЫТИЕ и ПОГРУЖЕНИЕ должна быть заменена строкой “index[name[i]]:= i;”
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
procedure LDG_DIJKSTRA_D-HEAP (var dist; var up; ADJ; n,d,s);
begin 
    for i:= 1 to n do begin
        up[i]:= 0; dist[i]:= +; index[i]:= i; name[i]:= i; key[i]:= +;
    end;
    key[s]:= 0; nq:= n; ОБРАЗОВАTЬ_ОЧЕРЕДЬ(name,key,nq,d);
    while nq>0 do begin
        ИЗЪЯТИЕ_МИНИМУМА(name1,key1,name,key,nq,d);
        i:= name1; dist[i]:= key1;
        p:= ADJ[i].next;
        while p ≠ nil do begin j:= p^.name; jq:= index[j];
{*}         if dist[jq] = +then 
                                                             if key[jq] > dist[i]+p^.w then begin
                key[jq]:= dist[i]+p^.w;
                ВСПЛЫТИЕ( jq,name,key,nq,d); up[j]:= i;
            end;
            p:= p^.next;
        end;
    end;
end;
Временная сложность алгоритма Дейкстры, реализованного на основе d-кучи, где d2, оценивается сверху величиной O((n+m)log n), так как алгоритм производит n ИЗЪЯТИЙ_МИНИМУМА и не более m ВСПЛЫТИЙ, каждое из которых осуществляется за время O(log n). Заметим также, что строку {*} можно убрать без какого бы то ни было влияния на правильность работы алгоритма.

Добавлено через 3 минуты
только я в нем ничего не понял. + есть обрывчатые мануалы на английском. типа этого:http://algorithms.soc.srcf.net/notes/dijkstra_with_heaps.pdf

Добавлено через 2 минуты
внезапно, нашел что-то на гуглокоде. Но все не то. Мне объяснение нужно, а не код. Да и не на плюсах он мне нужен
https://code.google.com/p/coding-templates/wiki/Dijkstra_sparse
0
Psilon
Master of Orion
Эксперт .NET
6058 / 4916 / 903
Регистрация: 10.07.2011
Сообщений: 14,520
Записей в блоге: 5
Завершенные тесты: 4
31.03.2014, 00:20 4
Смирняга, ну судя по всему это то же самое, только добавляется массив "имен" вершин.

И при чем тут С++?..
1
Смирняга
71 / 16 / 2
Регистрация: 29.12.2010
Сообщений: 339
31.03.2014, 00:32  [ТС] 5
просто это пример на плюсах. Других не нашел
А в чем суть добавлять массив вершин? Как он используется?
0
Psilon
Master of Orion
Эксперт .NET
6058 / 4916 / 903
Регистрация: 10.07.2011
Сообщений: 14,520
Записей в блоге: 5
Завершенные тесты: 4
31.03.2014, 01:27 6
Смирняга, ну вот в моем примере выше (на шарпе) идет поиск кратчайшего пути из какой-то вершины. Достаточно просто ввести еще массив имен, и все, типа
C#
1
string[] names = { "Москва", "СПБ", "Иркутск", "Воронеж", "Краснодар"};
после этого
C#
1
2
3
4
            for (int i = 0; i < costs.Length; i++)
            {
                Console.WriteLine("Пункт {0}, стоимость пути = {1}", names[i], costs[i]);
            }
0
Смирняга
71 / 16 / 2
Регистрация: 29.12.2010
Сообщений: 339
31.03.2014, 03:33  [ТС] 7
Та не. Они как-то приплели кучу, чтобы ускорять алгоритм. Куча имеется ввиду не обычная. А в виде дерева
0
31.03.2014, 03:33
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.03.2014, 03:33

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

Алгоритм Дейкстры (нахождение кратчайшего пути)
Можно как то еще оптимизировать процедуру в плане скорости? или это предел для чистого QB? SUB...

Алгоритм Дейкстры, нахождение кратчайшего пути
Доброго времени суток всем! У меня вопрос. Написала программку для нахождения кратчайшего пути...


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

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

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