Реализация алгоритма кратчайшего пути на C# ⇐ C#

[Anonymous]

Мне нужно реализовать на C# сложный алгоритм, который мог бы эффективно определять кратчайший путь между узлами взвешенного графа. Структура графа основана на списках смежности, которые эффективно представляют связи между узлами. Одна из проблем, с которыми я сталкиваюсь, — это реализация сценариев, в которых граф может включать ребра с отрицательным весом. Это требует тщательного рассмотрения, чтобы гарантировать, что алгоритм сможет обрабатывать такие веса, сохраняя при этом правильное вычисление кратчайшего пути:
using System.Collections.Generic;

public class ShortestPathAlgorithm
{
private Dictionary graph;

public ShortestPathAlgorithm(Dictionary graph)
{
this.graph = graph;
}

public List FindShortestPath(int startNode, int endNode)
{
Dictionary distances = InitializeDistances(startNode);
Dictionary previousNodes = InitializePreviousNodes();
List unvisitedNodes = new List(graph.Keys);

while (unvisitedNodes.Count > 0)
{
int currentNode = GetClosestNode(unvisitedNodes, distances);
unvisitedNodes.Remove(currentNode);

foreach (var (neighbor, weight) in graph[currentNode])
{
int alternativeRoute = distances[currentNode] + weight;
if (alternativeRoute < distances[neighbor])
{
distances[neighbor] = alternativeRoute;
previousNodes[neighbor] = currentNode;
}
}
}

return BuildPath(startNode, endNode, previousNodes);
}

private Dictionary InitializeDistances(int startNode)
{
Dictionary distances = new Dictionary();
foreach (var node in graph.Keys)
{
distances[node] = int.MaxValue;
}
distances[startNode] = 0;
return distances;
}

private Dictionary InitializePreviousNodes()
{
Dictionary previousNodes = new Dictionary();
foreach (var node in graph.Keys)
{
previousNodes[node] = null;
}
return previousNodes;
}

private int GetClosestNode(List unvisitedNodes, Dictionary distances)
{
int minDistance = int.MaxValue;
int closestNode = -1;

foreach (var node in unvisitedNodes)
{
if (distances[node] < minDistance)
{
minDistance = distances[node];
closestNode = node;
}
}

return closestNode;
}

private List BuildPath(int startNode, int endNode, Dictionary previousNodes)
{
List shortestPath = new List();
int? currentNodePath = endNode;

while (currentNodePath != null)
{
shortestPath.Add(currentNodePath.Value);
currentNodePath = previousNodes[currentNodePath.Value];
}

shortestPath.Reverse();
return shortestPath;
}

public static void Main(string[] args)
{
var graph = new Dictionary()
{
{ 1, new List{ (2, 7), (3, 9), (6, 14) } },
{ 2, new List{ (1, 7), (3, 10), (4, 15) } },
{ 3, new List{ (1, 9), (2, 10), (4, 11), (6, 2) } },
{ 4, new List{ (2, 15), (3, 11), (5, 6) } },
{ 5, new List{ (4, 6), (6, 9) } },
{ 6, new List{ (1, 14), (3, 2), (5, 9) } }
};

var algorithm = new ShortestPathAlgorithm(graph);
var shortestPath = algorithm.FindShortestPath(1, 5);

Console.WriteLine("Shortest Path from Node 1 to Node 5:");
Console.WriteLine(string.Join(" -> ", shortestPath));
}
}```


Подробнее здесь: https://stackoverflow.com/questions/786 ... in-c-sharp