Поиск кратчайшего пути в графе С — это специфичная задача. Очень часто такая задача возникает перед разработчиками игр. Алгоритмы для подобного поиска бывают разные, некоторые из них созданы «на коленке» самими разработчиками.
Самым известным и популярным алгоритмом, с помощью которого происходит поиск кратчайшего пути в графе С, является метод Дейкстры.
Поиск кратчайшего пути в графе: метод Дейкстры
Граф — это сеть специальных узлов, соединенных ребрами. Визуально графом можно представить «кусок» карты с несколькими городами и соединяющими их дорогами.
Соответственно, в графах ребра будут разной длины, а скорость передачи и «стоимость» информации по ним будет разная. Именно для этого и осуществляют поиск кратчайшего пути в графе, чтобы «удешевить» передачу данных.
Метод Дейкстры можно применять, когда ребра в графе несут в себе положительное значение. При работе этого метода происходит вычисление суммы всех ребер от начального узла и подсчет кратчайшего пути, причем сумма стартового узла — это ноль, а все остальные узлы — это бесконечность.
Метод Дейкстры считается оконченным, только после того как были посещены все узлы графа. После этого рассматривается длина всех вероятных маршрутов и выбирается кратчайший путь.
Как осуществить поиск кратчайшего пути в графе С, применяя класс по методу Дейкстры
Пример того, как можно реализовать подобный поиск:
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();
}
}
Заключение
Поиск кратчайшего пути при помощи метода Дейкстры уже много раз показывал свою эффективность, поэтому имеет смысл начинать искать кратчайший путь именно с него. Если по каким-то причинам этот метод вам не подойдет, тогда смело пробуйте другие подходы.
Другое
