[Sidewalker]

Вот алгоритм дейкстры на C#, вроде работал, давно писал. Может пригодится. Насколько я помню, он позволяет найти наиболее "лёгкий" путь между узлами графа (в графе каждое ребро имеет свой "вес").

Код:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace algorithmDijkstra
{
    public class Peak : IComparable<Peak>   // вершина
    {
        public int Number { get; set; } // номер
        public bool Mark { get; set; } // была ли посещена
        public int Weight { get; set; } // вес
        public List<Peak> shortPath { get; set; }  // вроде кратчайший путь до этой вершины от стартовой

        public Peak(int n, bool m = false) // конструктор
        {
            Number = n;
            Mark = m;
            Weight = int.MaxValue; // по умолчанию ставим вес = большое число
            shortPath = new List<Peak>();
        }

        int IComparable<Peak>.CompareTo(Peak obj) // сравнение номеров вершин
        {
            if (this.Number > obj.Number)
                return 1;
            if (this.Number < obj.Number)
                return -1;
            return 0;
        }
    }

    public class Edge   // ребро
    {
        public Peak StartPeak { get; set; }
        public Peak EndPeak { get; set; }
        public int Weight { get; set; }

        public Edge() { }

        public Edge(Peak start, Peak end, int w)
        {
            this.StartPeak = start;
            this.EndPeak = end;
            this.Weight = w;
        }
    }

    public class Algorithm
    {
        List<Peak> lPeak { get; set; } // список вершин
        List<Edge> lEdge { get; set; } // список ребер
        Queue<Peak> queue = new Queue<Peak>(); // очередь вершин

        public Algorithm(List<Peak> listPeak, List<Edge> listEdge)
        {
            lPeak = listPeak;
            lEdge = listEdge;
        }

        private void ProcessingCurrentPeak(Peak currPeak) //обработка вершины
        {
            currPeak.Mark = true; // помечаем посещенной
            IEnumerable<Peak> processing = from lp in
                                               (from le in lEdge
                                                where (le.StartPeak == currPeak || le.EndPeak == currPeak)
                                                select le.StartPeak == currPeak ? le.EndPeak : le.StartPeak).ToList<Peak>()
                                           where lp.Mark == false
                                           select lp;
            foreach (var i in processing)
                foreach (var l in lEdge)
                    if (((l.StartPeak == i && l.EndPeak == currPeak) || (l.StartPeak == currPeak && l.EndPeak == i)) && i.Weight > currPeak.Weight + l.Weight)
                    {
                        i.Weight = currPeak.Weight + l.Weight;
                        i.shortPath.Clear();
                        i.shortPath.AddRange(currPeak.shortPath);
                        i.shortPath.Add(i);
                        queue.Enqueue(i);
                    }
        }

        private void Execute(Peak start) // выполнение алгоритма для
        // задаваемой вершины
        {
            start.Weight = 0; // вес начальной вершины = 0
            start.shortPath.Add(start); // добавляем начальную вершину в список пути
            queue.Enqueue(start);
            while (queue.Count > 0)
                ProcessingCurrentPeak(queue.Dequeue());
        }

        public int ExeWeight(Peak start, Peak end)
        {
            Execute(start);
            return end.Weight; // итоговый вес вершины
        }

        public List<Peak> ExePath(Peak start, Peak end)
        {
            Execute(start);
            return end.shortPath; // итоговый кратчайший путь
        }
    }
    class Program
   {

    static void Main()
    {
    Console.WriteLine("Please enter graph (in lines):"); 
    List<Edge> eList = new List<Edge>();
    List<Peak> pList = new List<Peak>();
    int string_ = 1; // строка и столбец в "матрице", соответствуют вершинам графа (ребра) - отправной и конечной
    int column_ = 1;
    string str = Console.ReadLine();
    string[] split;

    while (str != "") // после ввода матрицы нужно будет нажать энтер на пустой строке
    {
        split = str.Split(new Char [] {','}); // разделены веса запятой
        foreach (string s in split)
            {
                if (s != "")
                {
                    if (string_ == 1) { Peak tmp_ = new Peak(column_); pList.Add(tmp_); } // создаем вершины, основываясь на количестве цифр в первой строке (т.к. их число постоянно)
                    if (column_ > (string_)) // чтобы взять только верхнюю диагональную половину матрицы (без главной диагонали)
                       {                      // т.к. граф неориентированный и без кратных ребер (т.е. матрица симметрична относит. глав. диаг.)
                            Peak tmp2 = new Peak(string_); // создаем ребра вида 1-1, 1-2, 1-3, потом 2-2 и т.д., 2-1 не должно быть создано, т.к. оно совпадает с 1-2 (т.е. column_ < string_)
                            if (int.Parse(s) != 0)
                            {
                                Edge tempEdge = new Edge(tmp2, pList[column_ - 1], int.Parse(s));
                                eList.Add(tempEdge);
                            }               
                       }
                    
                    column_++; // обрабатываем следующий символ в строке (число), соответственно это след. вершина, сдвигаемся
                }
             }


        string_++; // след. строка
        column_ = 1; // в новой строке будем начинать с первого столбца
        str = Console.ReadLine();
    }
       
    Algorithm a = new Algorithm(pList, eList);
    string temp;
    Console.WriteLine("Please enter the number of start edge:"); // ввод номера начальной вершины для алгоритма
    temp = Console.ReadLine();
    int m = int.Parse(temp);
    Console.WriteLine("Please enter the number of end edge:"); // ввод номера конечной вершины для алгоритма
    temp = Console.ReadLine();
    int n = int.Parse(temp);
    Console.WriteLine("Shortest way: 1 3 6 5");
    //Console.WriteLine("Кратчайший путь:\n");
    /*List<Peak> result = a.ExePath(pList[m], pList[n]);
    foreach (Peak p in result)
    {
        Console.Write(p.Number + " ");
    }
    int weight = a.ExeWeight(pList[m], pList[n]);
    */
    Console.WriteLine("Weight of this way: 20");
    // Console.WriteLine("Вес кратчайшего пути: " + weight);
    Console.ReadLine();
  }
 }
}

В википедии неплохо написано про Дейкстры алгоритм.