Алгоритм Дейкстры

Алгоритм Дейкстры – алгоритм для поиска кратчайшего пути между двумя заданными вершинами графа.

Алгоритм можно использовать для графов с положительными значениями весов ребер.

Описание алгоритма Дейкстры

Для каждой вершины графа вычисляется сумма весов ребер(расстояние) от начальной вершины.

Инициализация

Сумма весов для стартовой вершины устанавливается в ноль, а для всех остальных – бесконечность. Это показывает что расстояние до других вершин неизвестны. Все кроме первой вершины помечаются как непосещенные.

Итерации алгоритма

Алгоритм завершается как только все вершины посещены. В ином случае, из непосещенных вершин, выбирается та, у которой меньшая сумма весов. Затем рассматриваются все маршруты, в которых выбранная вершина стоит на предпоследнем месте.

Для описания графа используются классы из статьи Граф.

Класс для описания информации о вершинах графа

/// <summary>
/// Информация о вершине
/// </summary>
public class GraphVertexInfo
{
    /// <summary>
    /// Вершина
    /// </summary>
    public GraphVertex Vertex { get; set; }

    /// <summary>
    /// Не посещенная вершина
    /// </summary>
    public bool IsUnvisited { get; set; }

    /// <summary>
    /// Сумма весов ребер
    /// </summary>
    public int EdgesWeightSum { get; set; }

    /// <summary>
    /// Предыдущая вершина
    /// </summary>
    public GraphVertex PreviousVertex { get; set; }

    /// <summary>
    /// Конструктор
    /// </summary>
    /// <param name="vertex">Вершина</param>
    public GraphVertexInfo(GraphVertex vertex)
    {
        Vertex = vertex;
        IsUnvisited = true;
        EdgesWeightSum = int.MaxValue;
        PreviousVertex = null;
    }
}

Класс с реализацией поиска кратчайшего пути

using System.Collections.Generic;

/// <summary>
/// Алгоритм Дейкстры
/// </summary>
public class Dijkstra
{
    Graph graph;

    List<GraphVertexInfo> infos;

    /// <summary>
    /// Конструктор
    /// </summary>
    /// <param name="graph">Граф</param>
    public Dijkstra(Graph graph)
    {
        this.graph = graph;
    }

    /// <summary>
    /// Инициализация информации
    /// </summary>
    void InitInfo()
    {
        infos = new List<GraphVertexInfo>();
        foreach (var v in graph.Vertices)
        {
            infos.Add(new GraphVertexInfo(v));
        }
    }

    /// <summary>
    /// Получение информации о вершине графа
    /// </summary>
    /// <param name="v">Вершина</param>
    /// <returns>Информация о вершине</returns>
    GraphVertexInfo GetVertexInfo(GraphVertex v)
    {
        foreach (var i in infos)
        {
            if (i.Vertex.Equals(v))
            {
                return i;
            }
        }

        return null;
    }

    /// <summary>
    /// Поиск непосещенной вершины с минимальным значением суммы
    /// </summary>
    /// <returns>Информация о вершине</returns>
    public GraphVertexInfo FindUnvisitedVertexWithMinSum()
    {
        var minValue = int.MaxValue;
        GraphVertexInfo minVertexInfo = null;
        foreach (var i in infos)
        {
            if (i.IsUnvisited && i.EdgesWeightSum < minValue)
            {
                minVertexInfo = i;
                minValue = i.EdgesWeightSum;
            }
        }

        return minVertexInfo;
    }

    /// <summary>
    /// Поиск кратчайшего пути по названиям вершин
    /// </summary>
    /// <param name="startName">Название стартовой вершины</param>
    /// <param name="finishName">Название финишной вершины</param>
    /// <returns>Кратчайший путь</returns>
    public string FindShortestPath(string startName, string finishName)
    {
        return FindShortestPath(graph.FindVertex(startName), graph.FindVertex(finishName));
    }

    /// <summary>
    /// Поиск кратчайшего пути по вершинам
    /// </summary>
    /// <param name="startVertex">Стартовая вершина</param>
    /// <param name="finishVertex">Финишная вершина</param>
    /// <returns>Кратчайший путь</returns>
    public string FindShortestPath(GraphVertex startVertex, GraphVertex finishVertex)
    {
        InitInfo();
        var first = GetVertexInfo(startVertex);
        first.EdgesWeightSum = 0;
        while (true)
        {
            var current = FindUnvisitedVertexWithMinSum();
            if (current == null)
            {
                break;
            }

            SetSumToNextVertex(current);
        }

        return GetPath(startVertex, finishVertex);
    }    

    /// <summary>
    /// Вычисление суммы весов ребер для следующей вершины
    /// </summary>
    /// <param name="info">Информация о текущей вершине</param>
    void SetSumToNextVertex(GraphVertexInfo info)
    {
        info.IsUnvisited = false;
        foreach (var e in info.Vertex.Edges)
        {
            var nextInfo = GetVertexInfo(e.ConnectedVertex);
            var sum = info.EdgesWeightSum + e.EdgeWeight;
            if (sum < nextInfo.EdgesWeightSum)
            {
                nextInfo.EdgesWeightSum = sum;
                nextInfo.PreviousVertex = info.Vertex;
            }
        }
    }

    /// <summary>
    /// Формирование пути
    /// </summary>
    /// <param name="startVertex">Начальная вершина</param>
    /// <param name="endVertex">Конечная вершина</param>
    /// <returns>Путь</returns>
    string GetPath(GraphVertex startVertex, GraphVertex endVertex)
    {
        var path = endVertex.ToString();
        while (startVertex != endVertex)
        {
            endVertex = GetVertexInfo(endVertex).PreviousVertex;
            path = endVertex.ToString() + path;
        }

        return path;
    }
}

Программа для поиска кратчайшего пути между заданными вершинами графа с использованием алгоритма Дейкстры

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var g = new Graph();

        //добавление вершин
        g.AddVertex("A");
        g.AddVertex("B");
        g.AddVertex("C");
        g.AddVertex("D");
        g.AddVertex("E");
        g.AddVertex("F");
        g.AddVertex("G");

        //добавление ребер
        g.AddEdge("A", "B", 22);
        g.AddEdge("A", "C", 33);
        g.AddEdge("A", "D", 61);
        g.AddEdge("B", "C", 47);
        g.AddEdge("B", "E", 93);
        g.AddEdge("C", "D", 11);
        g.AddEdge("C", "E", 79);
        g.AddEdge("C", "F", 63);
        g.AddEdge("D", "F", 41);
        g.AddEdge("E", "F", 17);
        g.AddEdge("E", "G", 58);
        g.AddEdge("F", "G", 84);

        var dijkstra = new Dijkstra(g);
        var path = dijkstra.FindShortestPath("A", "G");
        Console.WriteLine(path);
        Console.ReadLine();
    }
}