Введение
Всем привет, пишу данный топик как логическое продолжение данной статьи о максимальном потоке минимальной стоимости, в конце которой был затронут алгоритм Дейксты. Соглашусь с автором, что описание и различные реализации алгоритма можно найти без проблем, и «колесо» я не изобретаю, но тем не менее опишу здесь практическую реализацию на языке C#. Кстати отмечу, что использую LINQ, так что для работы необходим NET 3.5.
UPDНаконец-то подчистил код :)
Немного теории
Чтобы сразу не кидали камни в мой огород дам ссылку на очень хорошее описание алгоритма на таком незаметном ресурсе как Википедия :). Там вполне доступно описан алгоритм и особенно рекомендую посмотреть пример. Копировать оттуда материал считаю бессмысленно. Все, считаем что теорию изучили.
Начало
Данный код представляет реализацию алгоритма на взвешенном неориентированном графе. Рассмотрим реализацию этого алгоритма.
Объектами данного алгоритма являются три класса:
• Apoint – класс, реализующий вершину графа
• Rebro – класс, реализующий ребро графа
• DekstraAlgoritm – класс, реализующий алгоритм Дейкстры.
Рассмотрим подробнее данные классы и самые важные методы.
APoint
Данный класс содержит в себе 5 полей:
•public float ValueMetka { get; set; } данное поле отвечает за хранение значений метки данной вершины. В программе под бесконечностью берется очень большое число, например 99999.
•public string Name { get; set; } – имя метки. Данное поле необходимо лишь для выведения удобно читаемого результата.
•public bool IsChecked { get; set; } – означает помечена метка или нет
•public APoint predPoint { get; set; } – «предок» точки, т.е. та точка которая является предком текущей в кратчайшем маршруте.
•public object SomeObj { get; set; } – некий объект
Каких-либо значимых методов данный класс не содержит.
Rebro
Данный класс содержит 3 поля:
•public APoint FirstPoint { get; set; } – начальная вершина ребра
•public APoint SecondPoint { get; set; } – конечная вершина ребра
•public float Value { get; set; } – весовой коэффициент.
Каких-либо значимых методов данный класс не содержит.
DekstraAlgorim
Данный класс представляет собой граф и реализацию алгоритма Дейкстры. Содержит 2 поля:
•public APoint[] points { get; set; } – массив вершин
•public Rebro[] rebra { get; set; }- массив ребер
Таким образом, эти 2 массива отражают граф. Рассмотрим методы:
•private APoint GetAnotherUncheckedPoint()
Данный метод возвращает очередную неотмеченную вершину, наименее удаленную, согласно алгоритму.
•public void OneStep(APoint beginpoint)
Данный метод делает один шаг алгоритма для заданной точке.
•private IEnumerable Pred(APoint currpoint)
Данный метод ищет соседей для заданной точки и возвращает коллекцию точек.
•public string MinPath(APoint begin,APoint end)
Данный метод возвращает кратчайший путь, найденный в алгоритме от начальной точке до конечной. Этот метод используется для наглядного отображения пути
•public void AlgoritmRun(APoint beginp)
Данный метод запускает алгоритм и принимает в качестве входа начальную точку.
Все основные методы описаны, представим процесс работы алгоритма в целом на рис.1. Основной метод OneStep представлен на рисунке 2.
Рис.1. Работа алгоритма в целом
Рис.2. Работа метода OneStep
Код
Наконец, рассмотрим сам код. В каждом классе написал подробные комментарии.
/// <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.Результат работы
Вот пример работы алгоритма для графа, описанного в теории:
point name=1, point value=0, predok=нет предка
point name=2, point value=9999, predok=нет предка
point name=3, point value=9999, predok=нет предка
point name=4, point value=9999, predok=нет предка
point name=5, point value=9999, predok=нет предка
point name=6, point value=9999, predok=нет предка
===========
point name=1, point value=0, predok=нет предка
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
Кратчайшие пути
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
Заключение
Просьба особо не пинать, моя 1 статья :) Любые замечания приветствую! Надеюсь, кому-нибудь код понадобится.
