Другое

Поиск кратчайшего пути в графе C: кратчайшие алгоритмы решения задачи

Lorem ipsum dolor

Поиск кратчайшего пути в графе С — это специфичная задача. Очень часто такая задача возникает перед разработчиками игр. Алгоритмы для подобного поиска бывают разные, некоторые из них созданы «на коленке» самими разработчиками.

Самым известным и популярным алгоритмом, с помощью которого происходит поиск кратчайшего пути в графе С, является метод Дейкстры.

 

Поиск кратчайшего пути в графе: метод Дейкстры

Граф — это сеть специальных узлов, соединенных ребрами. Визуально графом можно представить «кусок» карты с несколькими городами и соединяющими их дорогами.

Соответственно, в графах ребра будут разной длины, а скорость передачи и «стоимость» информации по ним будет разная. Именно для этого и осуществляют поиск кратчайшего пути в графе, чтобы «удешевить» передачу данных.

Метод Дейкстры можно применять, когда ребра в графе несут в себе положительное значение. При работе этого метода происходит вычисление суммы всех ребер от начального узла и подсчет кратчайшего пути, причем сумма стартового узла — это ноль, а все остальные узлы — это бесконечность.

Метод Дейкстры считается оконченным, только после того как были посещены все узлы графа. После этого рассматривается длина всех вероятных маршрутов и выбирается кратчайший путь.

 

Как осуществить поиск кратчайшего пути в графе С, применяя класс по методу Дейкстры

Пример того, как можно реализовать подобный поиск:

using System.Collection.Generic;

public class Dejkstra

{

Graf graf;

 

Lists info;

public Dejkstra(Graf graf)

{

this.graf = graf;

}

 

void InitInfos()

{

info = new List();

foreach (var v in graf.Vertices)

{

info.Add(new GrafNodeInfo(v));

}

}

 

GrafNodeInfo GetNodeInfo(GrafNode v)

{

foreach (var e in info)

{

if (e.Node.Equals(v))

{

return e;

}

}

 

return null;

}

public GrafNodeInfo FindUnvisitedNodeWithMinimumSum()

{

var minValue = int.MaxValue;

GrafNodeInfo minNodeInfo = null;

foreach (var e in info)

{

if (e.IsUnvisited && e.EdgesWeightSum< minValue)

{

minNodeInfo = e;

minValue = e.EdgesWeightSum;

}

}

 

return minNodeInfo;

}

public string FindShortPath(string startTitle, string finishTitle)

{

return FindShortPath(graf.FindNode(startTitle), graph.FindNode(finishTitle));

}

public string FindShortPath(GrafNode startNode, GrafNode finishNode)

{

InitInfos();

var first = GetNodeInfo(startNode);

first.SidesWeightSum = 0;

while (true)

{

var current = FindUnvisitedNodeWithMinimumSum();

if (current == null)

{

break;

}

 

SetSumToNextNode(current);

}

 

return GetPath(startNode, finishNode);

}

void SetSumToNextNode(GrafNodeInfo info)

{

info.IsUnvisited = false;

foreach (var e in info.Node.Sides)

{

var nextInfo = GetNodeInfo(e.ConnectedNode);

var sum = info.SidesWeightSum + e.EdgeWeight;

if (sum< nextInfo.SidesWeightSum)

{

nextInfo.SidesWeightSum = sum;

nextInfo.PreviousNode = info.Node;

}

}

}

 

string GetPath(GrafNode startNode, GrafNode endNode)

{

var path = endNode.ToString();

while (startNode != endNode)

{

endNode = GetNodeInfo(endNode).PreviousNode;

path = endNode.ToString() + path;

}

 

return path;

}

}

 

Поиск кратчайшего пути в графе С при помощи программы, применяя метод Дейкстры

Пример программы будет выглядеть так:

using System;

using System.Collections.Generic;

 

class Program

{

static void Main(string[] args)

{

var h = new Graf();

 

//добавляем узлы

h.AddNode("A");

h.AddNode("B");

h.AddNode("C");

h.AddNode("D");

h.AddNode("E");

h.AddNode("F");

h.AddNode("G");

//добавляем ребра

h.AddSide("A", "B", 23);

h.AddSide("A", "C", 34);

h.AddSide("A", "D", 62);

h.AddSide("B", "C", 48);

h.AddSide("B", "E", 94);

h.AddSide("C", "D", 12);

h.AddSide("C", "E", 80);

h.AddSide("C", "F", 64);

h.AddSide("D", "F", 42);

h.AddSide("E", "F", 18);

h.AddSide("E", "G", 59);

h.AddSide("F", "G", 84);

 

var dejkstra = new Dejkstra(h);

var path = dejkstra.FindShortestPath("A", "G");

Console.WriteLine(path);

Console.ReadLine();

}

}

 

Заключение

Поиск кратчайшего пути при помощи метода Дейкстры уже много раз показывал свою эффективность, поэтому имеет смысл начинать искать кратчайший путь именно с него. Если по каким-то причинам этот метод вам не подойдет, тогда смело пробуйте другие подходы.

Схожие статьи

Установка Windows на Raspberry PI 3. Детальная инструкция по шагам
Другое

Установка Windows на Raspberry PI 3. Детальная инструкция по шагам

Лучшие семинары для программистов: какие события IT нужно посетить?
Другое

Лучшие семинары для программистов: какие события IT нужно посетить?

Почему снижается работоспособность и как ее повысить
Другое

Почему снижается работоспособность и как ее повысить

Как убрать водяной знак с фотографии: самые удобные способы
Другое

Как убрать водяной знак с фотографии: самые удобные способы