using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace Dijistra{    public static class DijistraSeach    {        public class SearchResult        {            public int Distance { get; private set; }            public int[] Route { get; set; }            public SearchResult(int distance, int[] route)            {                Distance = distance;                Route = route;            }        }        /// <summary>        /// 获取正确的顺序<para/>        /// 比如footPrint为<para/>        /// [0] = 0<para/>        /// [1] = 0<para/>        /// [2] = 3<para/>        /// [3] = 0<para/>        /// [4] = 2<para/>        /// 从最后一行开始，[4] = 2，意味着[4]的前一个节点为[2]，然后看[2] = 3这一行，2的前节点为3，如此循环直到起点。        /// </summary>        /// <param name="footPrint">value -> index</param>        /// <param name="startPoint"></param>        /// <returns></returns>        private static int[] findRoute(int[] footPrint, int startPoint = 0)        {            var mapSize = footPrint.Length;            // 反向路径            var reversedRoute = new int[mapSize];            // 反向路径中的当前操作序号            int routeIndex = 0;            // 添加终点            reversedRoute[routeIndex] = mapSize - 1;            routeIndex++;            // 找到最末节点的前节点            int previousIndex = footPrint[mapSize - 1];            // 如果不是起点的话            while (previousIndex != startPoint)            {                // 路径不存在                if (previousIndex == -1)                    return null;                // 记录此节点并继续查找前节点                reversedRoute[routeIndex] = previousIndex;                routeIndex++;                previousIndex = footPrint[previousIndex];            }            // 添加起点            reversedRoute[routeIndex] = startPoint;            // 将反向路径反向            var route = new List<int>(mapSize);            for (int i = routeIndex; i >= 0; i--)            {                route.Add(reversedRoute[i]);            }            return route.ToArray();        }        /// <summary>        /// search for the shortest route.        /// </summary>        /// <param name="routes">an array which contains {pointA, pointB, distance}        /// <para/>e.g.        /// <para/>var map = new[] {        /// <para/>    new []{0,1,10},        /// <para/>    new []{0,3,30},        /// <para/>    new []{0,4,100},        /// <para/>    new []{1,2,50},        /// <para/>    new []{2,4,10},        /// <para/>    new []{3,2,20},        /// <para/>    new []{3,4,60},        /// <para/>};        /// </param>        /// <param name="mapSize">size</param>        /// <param name="startPoint"></param>        /// <param name="directional"></param>        /// <returns></returns>        public static SearchResult Search(int[][] routes, int mapSize, int startPoint , bool directional)        {            // record all minIndex found during the searching progress.            var footPrint = new int[mapSize];            // to avoid dead searching loop.            var visted = new bool[mapSize];            // accumulated distance from startPoint to each index.            var milestones = new int[mapSize];            // initialize map.            var map = new int[mapSize, mapSize];            for (int i = 0; i < mapSize; i++)            {                for (int j = 0; j < mapSize; j++)                {                    map[i, j] = i == j? 0 : int.MaxValue;                }            }            // build map.            foreach (var route in routes)            {                map[route[0], route[1]] = route[2];                if (!directional)                {                    // make the map non-directional.                    map[route[1], route[0]] = route[2];                }            }            // initialize milestones by distance between each node and startPoint.            for (int i = 0; i < mapSize; i++)            {                milestones[i] = map[startPoint, i];                // wether i is connected to startPoint or not;                if (milestones[i] != int.MaxValue)                {                    footPrint[i] = startPoint;                }                else                {                    footPrint[i] = -1;                }            }            // start searching.            for (int j = 0; j < mapSize; j++)            {                // find the nearest from this index.                // milestones has already been updated to fit the minIndex.                int localMin = int.MaxValue, minIndex = startPoint;                for (int i = 0; i < mapSize; i++)                {                    if (!visted[i] && milestones[i] < localMin)                    {                        minIndex = i;                        localMin = milestones[i];                    }                }                visted[minIndex] = true;                // update milestones.                for (int i = 0; i < mapSize; i++)                {                    // index not connected to minIndex is not connected to                     if (map[minIndex, i] == int.MaxValue) continue;                    if (visted[i]) continue;                    // accumulate distance from startPoint to minIndex;                    var newDis = milestones[minIndex] + map[minIndex, i];                    if ((newDis < milestones[i]))                    {                        milestones[i] = newDis;                        footPrint[i] = minIndex;                    }                }            }            // the end is beyond reach.            if (milestones[mapSize - 1] == int.MaxValue)                return null;            var resultRoute = findRoute(footPrint, startPoint);            var result = new SearchResult(milestones[mapSize - 1], resultRoute);            return result;        }    }}

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace Dijistra{    class Program    {        static void Main(string[] args)        {            // 无向图            // 使用此外图时，需将DijistraSeach.Search的directional参数设为false，mapSize=5            var nonDirectionalMap = new[] {                new []{0,1,10},                new []{0,3,30},                new []{0,4,100},                new []{1,2,50},                new []{2,4,10},                new []{3,2,20},                new []{3,4,60},            };            // 有向图            // 使用此外图时，需将DijistraSeach.Search的directional参数设为true，mapSize=2            var directionalMap = new[]{                new []{1, 0, 10},                new []{0, 1, 11},            };            var result = DijistraSeach.Search(                routes: nonDirectionalMap,                mapSize: 5,                startPoint: 0,                directional: false                );            if (result == null)            {                Console.WriteLine("Can‘t find the route.");            }            else            {                Console.WriteLine(                "Shortest distance is {0}\nroute : {1}\n",                result.Distance,                String.Join("->", result.Route)                );            }                    }    }}