Tag Archives: граф

Алгоритъмът на Дейкстра, реализиран с приоритетна опашка и написан на C#

Кой е Дейкстра?

Едсхер Дейкстра е холандски учен със значителни постижения в компютърните науки:
dijkstra

  • Независимо, заедно с колегата си Фридрих Бауер, са преоткрили алгоритъма обратен полски запис. Целяли са да намалят ползваната компютърна памет като използват стека за правене на изчисления.
  • Създател на алгоритма Shunting yard, който се използва за преобразуване на нормален израз в обратен полски запис.
  • Създател на алгоритъмът на Дейкстра, който открива най-кратък път в граф с положителни ребра.
  • Създал концепцията за семафора, която цели координация на множество програми и процесори.
  • Създател на алгоритъма на Банкер.
  • Един от създателите на първия компилатор на ALGOL 60. Двамата с неговия колега Яп Зонфилд си обещали да не се бръснат, докато не приключат компилатора. Създаденият компилатор бил един от първите, поддържащи рекурсия.
  • Голям противник на GOTO, той пишел статии срещу тази конструкция и спомогнал много за всеобщото й неодобрение. Заедно с това той прокарал идеята си за структурно програмиране, което вместо GOTO използва WHILE и FOR в кратки програмни блокове и избягва спагети кода.
  • Създал концепцията самостоятелна стабилизация, чиято цел била да накара една система да завърши правилно работата си при каквито и да е входни данни. Благодарение на откриването на тази концепция, Дейкстра е награден след близо 30 години с една от най-престижните награди в компютърното общество 2002 ACM PODC Influential-Paper Award, която по-късно е преименувана на “награда на Дейкстра”.
  • Награден с А.М. Тюринг

Алгоритми за най-кратък път в граф

Има различни алгоритми за намиране на най-кратък път граф – това е сумата на теглата на ребрата, през които минаваме от стартовия връх до целта. Три от най-известните алгоритми за намираме на най-кратките разстояния от конкретен връх до всички останали са алгоритмите на Форд-Белман, Флойд и Дейкстра.

И трита алгоритъма се основават на неравенството на триъгълника. Т.е. сумата на дължините на кои да е две страни е по-голяма от дължината на третата му страна. Всеки от тези алгоритми се основава на последователна проверка на (някои от) неравенствата на триъгълника и, в случай на нарушение, установяване в равенство.

Алгоритъмът на Форд-Белман има сложност Θ(n3). При него получаваме пътищата от стартовия връх до всички останали. Алгоритъмът работи с произволни тегла на ребрата – отрицателни и положителни. Полезно свойство на алгоритъма на Форд-Белман е, че позволява да се открие отрицателен цикъл, ако съществува такъв.

Алгоритъмът на Флойд е подобен на този на Форд-Белман. Той отново има сложност Θ(n3). След приключване на работата му обаче, при него получаваме разстоянията между всяка двойка върхове в графа. Отново, както при алгоритъма на Флойд, отрицателните ребра не са проблем, стига да няма отрицателни цикли.

Алгоритъмът на Дейкстра за най-кратък път в граф

Най-ефективният метод за намиране на най-кратките пътища от един връх до всички останали е алгоритъмът на Дейкстра. За да работи алгоритъмът, теглата трябва да са положителни. Повече информация за това как точно работи алгоритъма, както и анимации – тук. Сложността на алгоритъма е Θ(n2), но при използване на приоритетна опашка, тя може да спадне до Θ(n.log2n).

Алгоритъм на Дейкстра с приоритетна опашка, написан на C#

Понеже в библиотеката на C# няма реализация на приоритетна опашка, ще използваме класа OrderedBag<T> от колекцията Power Collections на Wintellect, която представлява сортирано мултимножество.

Първото нещо, което трябва да направим е един клас, който ще представя връх в граф. В него ще имаме – име на върха, цена, дали е бил посетен, кой е предишния връх, през който сме стигнали, за да стигнем до него и списък с децата му и цената(теглото на реброто) до всяко дете. Сорс-код:

class Vertex : IComparable<Vertex>
{
    public string Name { get; set; }
    public Vertex Previous { get; set; }
    public uint Cost { get; set; }
    public bool Visited { get; set; }
    public Dictionary<Vertex, uint> Children { get; set; }

    public Vertex(string name)
    {
        this.Name = name;
        this.Previous = null;
        this.Cost = int.MaxValue;
        this.Visited = false;
        this.Children = new Dictionary<Vertex, uint>();
    }
 
    public override bool Equals(Object obj)
    {
        if (this == obj)
        {
            return true;
        }

        Vertex other = obj as Vertex;
 
        if (other == null)
        {
            return false;
        }
 
        if (!this.Name.Equals(other.Name))
        {
            return false;
        }
        return true;
    }
 
    public override int GetHashCode()
    {
        return this.Name.GetHashCode();
    }

    public int CompareTo(Vertex other)
    {
        return this.Cost.CompareTo(other.Cost);
    }
}

Конструктора задава по подразбиране за предишен връх – null. Това ще ние полезно по-нататък при изпечатването на пътя. Задава се цена на пътя максималното int число. Ако реалната цена на пътя надвиши това число, алгоритъма няма да работи коректно. При необходимост, може да се промени на друго число или да се реализира по друг начин с цел избягване на препълване. Отбелязваме, че не е бил посетен. Децата пазим в речник, който хешира по име и пази в една променлива теглото на реброто към съответното дете. Теглата могат да са само положителни, тъй като алгоритъмът на Дейкстра работи само с такива.

Следва сорс-код на алгоритъма на Дейкстра:

static void ExecuteDijkstra(Vertex start)
{
    OrderedBag<Vertex> pQueue = new OrderedBag<Vertex>();
    start.Cost = 0;
    pQueue.Add(start);

    while (pQueue.Count > 0)
    {
        Vertex current = pQueue.RemoveFirst();
        current.Visited = true;
        foreach (Vertex child in current.Children.Keys)
        {
            if (child.Visited == false)
            {
                if (child.Cost > current.Cost + current.Children[child])
                {
                    child.Previous = current;
                    child.Cost = current.Cost + current.Children[child];
                    pQueue.Add(child);
                }
            }
        }
    }
}

За да намерим разстоянието от стартовия до текущия връх, се опитваме да оптимизираме с децата на текущия. За всяко дете, което е по-близко, го добавяме в приоритетната опашка. Докато не свършат върховете повтаряме процедурата като всеки път се обработва елементът, който е най-близо до стартовия връх.

Нека тестваме алгоритъма. Ще въведем неориентиран граф, но алгоритъмът работи също толкова успешно и с ориентиран:
dijkstra-algorithm-example-graph
Ще пуснем алгоритъма на Дейкстра от върха “A”. След това ще изпечатаме резултатите. Имаме разнообразни сценарии – има по няколко пътя до някои върхове, а до други – нямаме въобще. Можем да хард-коуд-нем графа по следния начин:

static void Main(string[] args)
{
    List<Vertex> graph = new List<Vertex>();
    graph.Add(new Vertex("A")); //0            
    graph.Add(new Vertex("B")); //1
    graph.Add(new Vertex("C")); //2
    graph.Add(new Vertex("D")); //3
    graph.Add(new Vertex("E")); //4
    graph.Add(new Vertex("F")); //5
    graph.Add(new Vertex("G")); //6
    graph.Add(new Vertex("H")); //7
    graph.Add(new Vertex("I")); //8
    graph.Add(new Vertex("J")); //9

    graph[0].Children.Add(graph[1], 23);
    graph[0].Children.Add(graph[7], 8);

    graph[1].Children.Add(graph[0], 23);
    graph[1].Children.Add(graph[3], 3);
    graph[1].Children.Add(graph[6], 34);

    graph[2].Children.Add(graph[7], 25);
    graph[2].Children.Add(graph[3], 6);
    graph[2].Children.Add(graph[9], 7);

    graph[3].Children.Add(graph[1], 3);
    graph[3].Children.Add(graph[2], 6);

    graph[4].Children.Add(graph[5], 10);

    graph[5].Children.Add(graph[4], 10);

    graph[6].Children.Add(graph[1], 34);

    graph[7].Children.Add(graph[0], 8);
    graph[7].Children.Add(graph[9], 30);
    graph[7].Children.Add(graph[2], 25);

    graph[9].Children.Add(graph[7], 30);
    graph[9].Children.Add(graph[2], 7);

    Vertex start = graph[0]; //"A"

    ExecuteDijkstra(start);
    PrintPaths(graph, start);
}

Функциите за отпечатване:

static void PrintPaths(List<Vertex> graph, Vertex start)
{
    foreach (Vertex vertex in graph)
    {
        if (vertex.Name != start.Name)
        {
            if (vertex.Cost == int.MaxValue)
            {
                Console.WriteLine("No path between " 
                    + start.Name + " and " + vertex.Name + ".");
            }
            else
            {
                Console.Write("The path between "
                    + start.Name + " and " + vertex.Name + " is: ");
                PrintPath(vertex);
                Console.WriteLine("and has a length of " + 
                    vertex.Cost + ".");
            }
        }
    }
}

static void PrintPath(Vertex v)
{
    if (v.Previous != null)
    {
        PrintPath(v.Previous);
    }
    Console.Write(v.Name + " ");
}

Как разпечатваме? Преминаваме през всеки връх на графа, с изключение на стартовия, и ако цената му е максималният int, значи не сме стигнали до него и той е в друга компонента на свързаност. Ако цената не е максималният int, значи сме стигнали до него по някакъв начин . Как да открием пътя? Помните ли, че записвахме в една променлива от кой връх сме дошли, за да стигнем до текущия. Остава да пуснем една изключителна проста рекурсия и да отпечатаме върха. Цялостната цена пазим в променливата Cost. Печатаме и нея. Резултата от изпълнението на всичкия код:
priority queue dijkstra algorithm graph example result