Программа находит кратчайший путь по алгоритму Дейкстры, как разобраться в коде - C#
Формулировка задачи:
У меня есть прога, которая находит кратчайший путь по алгоритму дейкстры, с графическим оформлением, нужна помощь с описанием работы данной проги, т.к. никак не могу разобраться что куда дописывать.
И нужно осуществить ввод веса ребер, и поиска кратчайшего пути по весу ребер.
Очень нужна помощь.
dejkstra.rar
Решение задачи: «Программа находит кратчайший путь по алгоритму Дейкстры, как разобраться в коде»
textual
Листинг программы
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication18
{
class Program
{
sealed public class Node
{
public List<Link> Links { get; set; }
public Node()
{
Links = new List<Link>();
}
}
sealed public class Link
{
public double Distance { get; set; }
public string Node { get; set; }
}
sealed public class Description
{
public bool Visited { get; set; }
public double Distance { get; set; }
public Description()
{
Visited = false;
Distance = double.PositiveInfinity;
}
}
sealed public class Graph
{
private Dictionary<string, Node> nodes;
public Graph()
{
nodes = new Dictionary<string, Node>();
}
public void AddNode(string name)
{
nodes.Add(name, new Node());
}
public void AddLinkToNode(string start, string end, double distance, bool isOriented)
{
nodes[start].Links.Add(new Link { Node = end, Distance = distance });
if (!isOriented)
nodes[end].Links.Add(new Link { Node = start, Distance = distance });
}
public double FindShortestDistance(string start, string end)
{
// Алгоритм Дейкстры.
Dictionary<string, Description> info = new Dictionary<string, Description>(this.nodes.Count);
foreach (string current in this.nodes.Keys)
info.Add(current, new Description());
info[start].Distance = 0;
// Пока все вершины непосещенные.
while (!info.Select(x => x.Value.Visited).Aggregate((x, y) => x & y))
{
// Находим непосещенную вершину с минимальной меткой.
string current = info.Where(x => !x.Value.Visited
&& x.Value.Distance == info.Where(y => !y.Value.Visited).Min(y => y.Value.Distance))
.First().Key;
// Находим все непосещенные соседние вершины для текущей вершины.
List<Link> neighbors = nodes[current].Links.Where(x => !info[x.Node].Visited).ToList();
// Рассматриваем новую длину пути для каждой соседней вершины.
foreach (Link link in neighbors)
{
double distance = info[current].Distance + link.Distance;
if (info[link.Node].Distance > distance)
info[link.Node].Distance = distance;
}
// Отмечаем текущую вершину как посещенная.
info[current].Visited = true;
}
return info[end].Distance;
}
}
static void Main()
{
int count = 6;
string[] names = { "A", "B", "C", "D", "E", "F" };
// Дан взвешенный ОРИЕНТИРОВАННЫЙ граф G(V,E) без петель и дуг отрицательного веса.
// Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.
// Все входные параметры методов данного графа считаются достоверными - нет проверок корректности параметров.
Graph graph = new Graph();
// Заполнение графа вершинами.
for (int i = 0; i < count; ++i)
graph.AddNode(names[i]);
// Создание у вершин связей.
// Последнее значение говорит о том, что эта связь двунаправленная.
graph.AddLinkToNode("A", "B", 7, false);
graph.AddLinkToNode("A", "C", 9, false);
graph.AddLinkToNode("A", "F", 14, false);
graph.AddLinkToNode("B", "C", 10, false);
graph.AddLinkToNode("B", "D", 15, false);
graph.AddLinkToNode("C", "D", 11, false);
graph.AddLinkToNode("C", "F", 2, false);
graph.AddLinkToNode("D", "E", 6, false);
graph.AddLinkToNode("E", "F", 9, false);
Console.WriteLine(graph.FindShortestDistance("A", "B")); // Ответ 7.
Console.WriteLine(graph.FindShortestDistance("A", "C")); // Ответ 9.
Console.WriteLine(graph.FindShortestDistance("A", "D")); // Ответ 20.
Console.WriteLine(graph.FindShortestDistance("A", "E")); // Ответ 20.
Console.WriteLine(graph.FindShortestDistance("A", "F")); // Ответ 11.
Console.ReadKey();
}
}
}