Implementing Dijkstra's C # Algorithm

Introduction

Hello everyone, I am writing this topic as a logical continuation of this article about the maximum flow of the minimum cost, at the end of which the Dakesta 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 for work.

UPD Finally cleaned up the code :)

A bit of theory

To not immediately throw stones in my garden I will give a link to a very good description of the algorithm on such an imperceptible resource like Wikipedia :). The algorithm is described there quite well and I especially recommend to see an example. I think copying material from there is pointless. All believe that the theory 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 - class that implements the top of the graph
• Rebro - class that implements the edge graph
• DekstraAlgoritm - a class that implements the Dijkstra algorithm.
Let's take a closer look at these classes and the most important methods.
Apoint
This class contains 5 fields:
• public float ValueMetka {get; set; } This field is responsible for storing the values ​​of the label of this vertex. In the program at infinity, a very large number is taken, for example, 99999.
• public string Name {get; set; } Is the name of the label. This field is only needed to derive a conveniently readable result.
• public bool IsChecked {get; set; } - means the label is marked or not
• public APoint predPoint {get; set; } - “ancestor” of the point, i.e. that point which is the ancestor of the current in the shortest route.
• public object SomeObj {get; set; } - some 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; } - finite 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 the Dijkstra algorithm. Contains 2 fields:
• public APoint [] points {get; set; } - array of vertices
• public Rebro [] rebra {get; set; } - 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 remote, 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 looks 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 starting point to the final. 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 basic OneStep method is presented in Figure 2.

Fig.1. The operation of the algorithm as a whole

Fig.2. OneStep method operation

Code

Finally, consider the code itself. In each class wrote detailed comments.

/// <summary>
/// .
/// </summary>
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;
}
/// <summary>
///
/// </summary>
/// <param name="beginp"></param>
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 ;
}

}
}

}
/// <summary>
/// , .
/// </summary>
/// <param name="beginpoint"></param>
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 ; //
}
/// <summary>
/// . .
/// </summary>
/// <param name="currpoint"></param>
/// <returns></returns>
private IEnumerable <Point> Pred(Point currpoint)
{
IEnumerable <Point> firstpoints = from ff in rebra where ff.FirstPoint==currpoint select ff.SecondPoint;
IEnumerable <Point> secondpoints = from sp in rebra where sp.SecondPoint == currpoint select sp.FirstPoint;
IEnumerable <Point> totalpoints = firstpoints.Concat<Point>(secondpoints);
return totalpoints;
}
/// <summary>
/// , 2
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
private Rebro GetMyRebro(Point a, Point b)
{ // 2
IEnumerable <Rebro> 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();
}
}
/// <summary>
/// , "" .
/// </summary>
/// <returns></returns>
private Point GetAnotherUncheckedPoint()
{
IEnumerable <Point> 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 <Point> MinPath1(Point end)
{
List <Point> listOfpoints = new List <Point>();
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 .

')

/// <summary>
/// ,
/// </summary>
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 .

/// <summary>
/// ,
/// </summary>
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 .

// <summary>
///
/// </summary>
static class PrintGrath
{
public static List < string > PrintAllPoints(DekstraAlgorim da)
{
List < string > retListOfPoints = new List < string >();
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 < string > PrintAllMinPaths(DekstraAlgorim da)
{
List < string > retListOfPointsAndPaths = new List < string >();
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 the 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 especially, my 1 article :) I welcome any comments! I hope someone will need the code.