The implementation of Dijkstra's algorithm in C #
Introduction
Hello everyone, I am writing this topic as a logical continuation of this article about the maximum flow of minimum cost, at the end of which the Dijksta algorithm was affected. I agree with the author that the description and various implementations of the algorithm can be found without problems, and I do not invent the “wheel”, but nevertheless I will describe here a practical implementation in C #. By the way, I note that I use LINQ, so NET 3.5 is required to work.
UPD Finally cleaned up the code :)
Bit of theory
So that they don’t immediately throw stones at my garden, I will give a link to a very good description of the algorithm on such an inconspicuous resource as Wikipedia :). The algorithm is described there quite well and I especially recommend looking at an example. Copying the material from there is pointless. Everything, we consider that the theory was studied.
Start
This code represents the implementation of the algorithm on a weighted undirected graph. Consider the implementation of this algorithm.
The objects of this algorithm are three classes:
• Apoint - a class that implements a vertex of a graph
• Rebro - a class that implements an edge of a graph
• DekstraAlgoritm - a class that implements Dijkstra's algorithm.
Let us consider these classes and the most important methods in more detail.
APoint
This class contains 5 fields:
• public float ValueMetka {get; set; } this field is responsible for storing the label values of this vertex. A very large number is taken under infinity in the program, for example 99999.
• public string Name {get; set; } Is the name of the label. This field is necessary only to derive a readable result.
• public bool IsChecked {get; set; } - means the label is marked or not
• public APoint predPoint {get; set; } - the "ancestor" of the point, i.e. the point that is the ancestor of the current in the shortest route.
• public object SomeObj {get; set; } - a certain object
This class does not contain any significant methods.
Rebro
This class contains 3 fields:
• public APoint FirstPoint {get; set; } - the initial vertex of the edge
• public APoint SecondPoint {get; set; } - end vertex of the edge
• public float Value {get; set; } - weight coefficient.
This class does not contain any significant methods.
DekstraAlgorim
This class is a graph and implementation of Dijkstra's algorithm. It contains 2 fields:
• public APoint [] points {get; set; } - an array of vertices
• public Rebro [] rebra {get; set; } - an array of edges.
Thus, these 2 arrays reflect the graph. Consider the methods:
• private APoint GetAnotherUncheckedPoint ()
This method returns the next unmarked vertex, the least removed, according to the algorithm.
• public void OneStep (APoint beginpoint)
This method takes one step of the algorithm for a given point.
• private IEnumerable Pred (APoint currpoint)
This method searches for neighbors for a given point and returns a collection of points.
• public string MinPath (APoint begin, APoint end)
This method returns the shortest path found in the algorithm from the start point to the end. This method is used to visualize the path
• public void AlgoritmRun (APoint beginp)
This method starts the algorithm and takes the starting point as input.
All the main methods are described; we will present the process of the algorithm as a whole in Fig. 1. The main OneStep method is shown in Figure 2.
Figure 1. The operation of the algorithm as a whole
Fig. 2. OneStep Method Operation
The code
Finally, consider the code itself. In each class he wrote detailed comments.
///
/// Реализация алгоритма Дейкстры. Содержит матрицу смежности в виде массивов вершин и ребер
///
class DekstraAlgorim
{
public Point[] points { get; private set; }
public Rebro[] rebra { get; private set; }
public Point BeginPoint { get; private set; }
public DekstraAlgorim(Point[] pointsOfgrath, Rebro[] rebraOfgrath)
{
points = pointsOfgrath;
rebra = rebraOfgrath;
}
///
/// Запуск алгоритма расчета
///
///
public void AlgoritmRun(Point beginp)
{
if (this.points.Count() == 0 || this.rebra.Count() == 0)
{
throw new DekstraException("Массив вершин или ребер не задан!");
}
else
{
BeginPoint = beginp;
OneStep(beginp);
foreach (Point point in points)
{
Point anotherP = GetAnotherUncheckedPoint();
if (anotherP != null)
{
OneStep(anotherP);
}
else
{
break;
}
}
}
}
///
/// Метод, делающий один шаг алгоритма. Принимает на вход вершину
///
///
public void OneStep(Point beginpoint)
{
foreach(Point nextp in Pred(beginpoint))
{
if (nextp.IsChecked == false)//не отмечена
{
float newmetka = beginpoint.ValueMetka + GetMyRebro(nextp, beginpoint).Weight;
if (nextp.ValueMetka > newmetka)
{
nextp.ValueMetka = newmetka;
nextp.predPoint = beginpoint;
}
else
{
}
}
}
beginpoint.IsChecked = true;//вычеркиваем
}
///
/// Поиск соседей для вершины. Для неориентированного графа ищутся все соседи.
///
///
///
private IEnumerable Pred(Point currpoint)
{
IEnumerable firstpoints = from ff in rebra where ff.FirstPoint==currpoint select ff.SecondPoint;
IEnumerable secondpoints = from sp in rebra where sp.SecondPoint == currpoint select sp.FirstPoint;
IEnumerable totalpoints = firstpoints.Concat(secondpoints);
return totalpoints;
}
///
/// Получаем ребро, соединяющее 2 входные точки
///
///
///
///
private Rebro GetMyRebro(Point a, Point b)
{//ищем ребро по 2 точкам
IEnumerable myr = from reb in rebra where (reb.FirstPoint == a & reb.SecondPoint == b) || (reb.SecondPoint == a & reb.FirstPoint == b) select reb;
if (myr.Count() > 1 || myr.Count() == 0)
{
throw new DekstraException("Не найдено ребро между соседями!");
}
else
{
return myr.First();
}
}
///
/// Получаем очередную неотмеченную вершину, "ближайшую" к заданной.
///
///
private Point GetAnotherUncheckedPoint()
{
IEnumerable pointsuncheck = from p in points where p.IsChecked == false select p;
if (pointsuncheck.Count() != 0)
{
float minVal = pointsuncheck.First().ValueMetka;
Point minPoint = pointsuncheck.First();
foreach (Point p in pointsuncheck)
{
if (p.ValueMetka < minVal)
{
minVal = p.ValueMetka;
minPoint = p;
}
}
return minPoint;
}
else
{
return null;
}
}
public List MinPath1(Point end)
{
List listOfpoints = new List();
Point tempp = new Point();
tempp = end;
while (tempp != this.BeginPoint)
{
listOfpoints.Add(tempp);
tempp = tempp.predPoint;
}
return listOfpoints;
}
* This source code was highlighted with Source Code Highlighter. ///
/// Класс, реализующий ребро
///
class Rebro
{
public Point FirstPoint { get; private set; }
public Point SecondPoint { get; private set; }
public float Weight { get; private set; }
public Rebro(Point first, Point second, float valueOfWeight)
{
FirstPoint = first;
SecondPoint = second;
Weight = valueOfWeight;
}
}
* This source code was highlighted with Source Code Highlighter.///
/// Класс, реализующий вершину графа
///
class Point
{
public float ValueMetka { get; set; }
public string Name { get; private set; }
public bool IsChecked { get; set; }
public Point predPoint { get; set; }
public object SomeObj { get; set; }
public Point(int value,bool ischecked)
{
ValueMetka = value;
IsChecked = ischecked;
predPoint = new Point();
}
public Point(int value, bool ischecked,string name)
{
ValueMetka = value;
IsChecked = ischecked;
Name = name;
predPoint = new Point();
}
public Point()
{
}
}
* This source code was highlighted with Source Code Highlighter.//
/// для печати графа
///
static class PrintGrath
{
public static List PrintAllPoints(DekstraAlgorim da)
{
List retListOfPoints = new List();
foreach (Point p in da.points)
{
retListOfPoints.Add(string.Format("point name={0}, point value={1}, predok={2}", p.Name, p.ValueMetka, p.predPoint.Name ?? "нет предка"));
}
return retListOfPoints;
}
public static List PrintAllMinPaths(DekstraAlgorim da)
{
List retListOfPointsAndPaths = new List();
foreach (Point p in da.points)
{
if (p != da.BeginPoint)
{
string s = string.Empty;
foreach (Point p1 in da.MinPath1(p))
{
s += string.Format("{0} ", p1.Name);
}
retListOfPointsAndPaths.Add(string.Format("Point ={0},MinPath from {1} = {2}", p.Name, da.BeginPoint.Name, s));
}
}
return retListOfPointsAndPaths;
}
}
* This source code was highlighted with Source Code Highlighter. class DekstraException:ApplicationException
{
public DekstraException(string message):base(message)
{
}
}
* This source code was highlighted with Source Code Highlighter.Work result
Here is an example of the algorithm for the graph described in theory:
point name = 1, point value = 0, predok = no ancestor
point name = 2, point value = 9999, predok = no ancestor
point name = 3, point value = 9999, predok = no ancestor
point name = 4, point value = 9999, predok = no ancestor
point name = 5, point value = 9999, predok = no ancestor
point name = 6, point value = 9999, predok = no ancestor
===== ======
point name = 1, point value = 0, predok = no ancestor
point name = 2, point value = 7, predok = 1
point name = 3, point value = 9, predok = 1
point name = 4 , point value = 20, predok = 3
point name = 5, point value = 20, predok = 6
point name = 6, point value = 11, predok = 3
Shortest paths
Point = 2, MinPath from 1 = 2
Point = 3, MinPath from 1 = 3
Point = 4, MinPath from 1 = 4 3
Point = 5, MinPath from 1 = 5 6 3
Point = 6, MinPath from 1 = 6 3
Conclusion
Please do not kick, my 1 article :) Any comments welcome! I hope someone needs the code.