Вернуться




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




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

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

 

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

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

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

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

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

 

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

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

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();

}

}

 

Заключение

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



Если вам понравилась эта статья поделитесь ею с друзьями, тем самым вы помогаете нам развиваться и добавлять всё больше интересного и полезного контента!




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





Стоит ли учиться программировать в 2021

Стоит ли учиться программировать в 2021

Не случайно в разговорах о рынке труда, перспективах развития и важнейших с ...

21 Февраля 2021    Другое


Плюсы и минусы Baas для разработки мобильных приложений

Плюсы и минусы Baas для разработки мобильных приложений

Если вы хотите заказать разработку мобильного приложения, причем чтобы вам ...

23 Марта 2021    Другое


Начинающий программист

Начинающий программист

Самыми легкими в изучении можно считать такие языки как JavaScript, Python, ...

23 Марта 2021    Другое




Напишем