Другое

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

}

}

 

Заключение

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

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

Предметно-ориентированное программирование. Достоинства и недостатки
Другое

Предметно-ориентированное программирование. Достоинства и недостатки

Как опубликовать игру в Steam: краткий пошаговый гайд для новичка
Другое

Как опубликовать игру в Steam: краткий пошаговый гайд для новичка

Расцвет и закат интегрированных пакетов
Другое

Расцвет и закат интегрированных пакетов

OpenCV поиск по шаблону. Примеры кода и объяснение с комментариями
Другое

OpenCV поиск по шаблону. Примеры кода и объяснение с комментариями