Другое

Поиск кратчайшего пути в графе 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();

}

}

 

Заключение

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

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

Архитектор программного обеспечения: главное об этой профессии
Другое

Архитектор программного обеспечения: главное об этой профессии

Парное программирование: как это работает и насколько эффективно?
Другое

Парное программирование: как это работает и насколько эффективно?

Типы групп Active Directory, для чего это нужно, как создать новую группу
Другое

Типы групп Active Directory, для чего это нужно, как создать новую группу

Windows 10 creators update: что это за обновление и нужно ли его устанавливать?
Другое

Windows 10 creators update: что это за обновление и нужно ли его устанавливать?

×