Алгоритм

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Graphs;
using Graphs.Algorithms;
 
namespace Lab2
{
    class DijkstraData
    {
        public int Distance { get; set; }
        public Vertex Previous { get; set; }
    }
 
    public static class AlgorithmDijkstra
    {
        public static List<Vertex> Compute(Graph graph, int[,] weightMatrix, Vertex start, Vertex end)
        {
            List<Vertex> notVisited = new List<Vertex>((IEnumerable<Vertex>)graph);
 
            var track = new Dictionary<Vertex, DijkstraData>();
            track[start] = new DijkstraData { Previous = null, Distance = 0 };
 
            while (true)
            {
                Vertex toEnter = null;
                int bestDistance = int.MaxValue;
 
                foreach (var vertex in notVisited)
                {
                    if (track.ContainsKey(vertex) && track[vertex].Distance < bestDistance)
                    {
                        toEnter = vertex;
                        bestDistance = track[vertex].Distance;
                    }
                }
                if (toEnter == end)
                    break;
                if (toEnter == null)
                    return null;
                
                string[] edgeList = graph.GetEdgeList();
                foreach (var edge in edgeList)
                {
                    string[] res = System.Text.RegularExpressions.Regex.Split(edge, @"[^0-9]+")
                                                                       .Where(p => !string.IsNullOrEmpty(p))
                                                                       .ToArray();
                    if (Convert.ToInt32(res[1]) == toEnter.Value || Convert.ToInt32(res[2]) == toEnter.Value)
                    {
                        
                        if (graph.VertexValue(Convert.ToInt32(res[1])) != toEnter && 
                            graph.VertexValue(Convert.ToInt32(res[2])) != toEnter)
                        {
                            continue;
                        }
 
                        Vertex nextVertex;
 
                        if (graph.VertexValue(Convert.ToInt32(res[1])) == toEnter)
                            nextVertex = graph.VertexValue(Convert.ToInt32(res[2]));
                        else
                            nextVertex = graph.VertexValue(Convert.ToInt32(res[1]));
 
                        var currentDistance = track[toEnter].Distance + 
                                              weightMatrix[graph.VertexValue(Convert.ToInt32(res[1])).Value - 1,
                                                           graph.VertexValue(Convert.ToInt32(res[2])).Value - 1];
 
                        if (!track.ContainsKey(nextVertex) || track[nextVertex].Distance > currentDistance)
                            track[nextVertex] = new DijkstraData { Distance = currentDistance, Previous = toEnter };
 
                    }
                }
                //
                notVisited.Remove(toEnter);
            }
            var result = new List<Vertex>();
            while (end != null)
            {
                result.Add(end);
                end = track[end].Previous;
            }
            result.Reverse();
            return result;
        }
    }
}