最短路径Dijkstra备忘

参考：

http://2728green-rock.blog.163.com/blog/static/43636790200901211848284/

http://hi.baidu.com/chin/blog/item/93aed933e6772443ad4b5f88.html

描述：

Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

 

说明：

V表示点集合，E表示边集合，图G=(V,E)表示图是由点集合与点之间的连线组成，如V={a,b,c,d}表示图G有a,b,c,d四个点，E={(a,b),(a,c),(c,d),(b,d)},表示图有a-b，a-c等边，一般<a,b>这样的尖括号表示有向边，(a,b) 这样的圆括号表示无向边。

 

有点集合V={a,b,c,d,e,f}

S表示已计算出最短路径（假设a为源点)的顶点集合 ，U表示除S中点以外的点的集合，U中每个点ui都对应着一个距离值a--ui（存在a到ui的边）,a--ui这个距离值可取无穷大（两点没有直接连线），或是经过S中的某一个或多个点a--si--ui的距离值。

1.S中第一个加入的点是a,加入a后a-a的距离是零，满足S中的点必需是计算出最短路径的要求.

2.接着在U中选择最短的a-ui,假设ui是d,将d加入集合S,此时S={a,d},然后尝试使用a-d-ui调整U={c,d,e,f}中每个点a--ui的距离（如果通过新加的d点使a--ui距离变短).

3.重复步骤2，直到U集合中没有点，算法结束S中将是a到任意点的最短距离。

 

 

 

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

namespace LycorisRadiata.UI.Craft
{
    public class Dijkstra
    {
        #region Model
        /// <summary>
        /// node
        /// </summary>
        public class N
        {
            public int Id { get; set; }
            public String Name { get; set; }
            public String Flag { get; set; }
            public String ExtendProperty { get; set; }
            public List<E> Edges { get; set; }
            public N()
            {
                Edges = new List<E>();
            }
            public N(int id)
                : this()
            {
                this.Id = id;
            }

        }
        /// <summary>
        /// edge
        /// </summary>
        public class E
        {
            public int ToId { get; set; }
            public decimal Len { get; set; }
            public E()
            {

            }
            public E(int toId, decimal len)
                : this()
            {
                this.ToId = toId;
                this.Len = len;
            }

        }
        public class NodeDistance
        {
            public int NodeId { get; set; }
            public int PreNodeId { get; set; }
            /// <summary>
            /// HasSelected=true时
            /// 这里记录了从出发点经过PreNodeId到该节点(NodeId)
            /// 最短距离--是累加的距离
            /// </summary>
            public decimal Distance { get; set; }
            /// <summary>
            /// 是否已经在最优集合里了
            /// </summary>
            public bool HasSelected { get; set; }
            public NodeDistance()
            {
                HasSelected = false;
            }
            public NodeDistance(int nodeId, int preNodeId, decimal len)
            {
                this.NodeId = nodeId;
                this.PreNodeId = preNodeId;
                this.Distance = len;
            }
        }

        /// <summary>
        /// 路径
        /// </summary>
        public class Route
        {
            /// <summary>
            /// StartIdToEndId
            /// </summary>
            public int StartId { get; set; }
            public int EndId { get; set; }

            public List<N> Nodes { get; set; }
            public String Way { get; set; }
            public decimal Distance { get; set; }
            public void CalcDistance()
            {

                var prevNode = Nodes[0];
                var dist = 0.0m;
                var sb = new StringBuilder();
                for (int i = 0; i < Nodes.Count; i++)
                {
                    var curNode = Nodes[i];
                    if (prevNode.Id == curNode.Id) continue;
                    var edge=prevNode.Edges.FirstOrDefault(e => e.ToId == curNode.Id);
                    dist +=edge.Len;
                    prevNode = curNode;
                    sb.AppendFormat("-{0}->[{1}]",  edge.Len,curNode.Id);
                }
                Distance = dist;
                Way ="[" + Nodes[0].Id +"]"  + sb.ToString() ;



            }
            public Route()
            {
                Nodes = new List<N>();
            }


        }
        #endregion

        private decimal[,] _G = null;
        private List<NodeDistance> _VSet;
        public List<Route> Calc(List<N> nodes, N start)
        {
            //InitGMatrix(nodes);完全用不到
            
            _VSet = new List<NodeDistance>();
            for (int i = 0; i < nodes.Count; i++)
            {
                _VSet.Add(new NodeDistance(i, start.Id, decimal.MaxValue));
            }

            var curDistInfo = _VSet[start.Id];//当前考察节点
            curDistInfo.Distance = 0;
            curDistInfo.HasSelected = true;
            var curNode = start;


            var iteration_max = 1000000;
            var iteration_count = 0;
            while (_VSet.Any(ent => ent.HasSelected == false))
            {
                iteration_count++;
                if (iteration_count > iteration_max) throw new Exception("算法迭代超过设置值!");

                #region 使用curNode调整VSet距离
                foreach (var edge in curNode.Edges)
                {

                    var dist = curDistInfo.Distance;
                    var inspectDist= _VSet.FirstOrDefault(ent =>ent.HasSelected==false && ent.NodeId == edge.ToId);//跳过已经标记的点
                    if (inspectDist == null) continue;
                    var newDist=dist+edge.Len;
                    if (inspectDist.Distance > newDist)
                    {
                        inspectDist.PreNodeId = curDistInfo.NodeId;
                        inspectDist.Distance = newDist;
                        
                    }

                }
                #endregion

                curDistInfo= _VSet.Where(ent => ent.HasSelected == false).OrderBy(ent => ent.Distance).FirstOrDefault();
                if (curDistInfo == null) break;
                curNode = nodes.FirstOrDefault(ent => ent.Id == curDistInfo.NodeId);
                curDistInfo.HasSelected = true;


            }
            var rList = new List<Route>();
            #region 生成结果
            foreach (var item in _VSet)
            {
                var curDistEnt = item;
                var route=new Route();
                rList.Add(route);
                route.StartId=start.Id;
                route.EndId = curDistEnt.NodeId;
                var node = nodes.FirstOrDefault(ent => ent.Id == curDistEnt.NodeId);
                route.Nodes.Add(node);
                while (curDistEnt.PreNodeId != start.Id)
                {
                    
                    node = nodes.FirstOrDefault(ent => ent.Id == curDistEnt.PreNodeId);
                    route.Nodes.Add(node);
                    curDistEnt = _VSet.FirstOrDefault(ent => ent.NodeId == curDistEnt.PreNodeId);
                }
                route.Nodes.Add(start);//加入起始节点
                route.Nodes.Reverse();
                route.CalcDistance();

            }
            #endregion
            return rList;
        }

        private void InitGMatrix(List<N> nodes)
        {
            _G = new decimal[nodes.Count, nodes.Count];
            for (int row = 0; row < nodes.Count; row++)
            {
                for (int col = 0; col < nodes.Count; col++)
                {
                    if (row == col)
                    {
                        _G[row, col] = 0;
                    }
                    else
                    {
                        _G[row, col] = decimal.MaxValue;
                    }
                }
            }
            #region 构建GMatrix
            foreach (var node in nodes)
            {
                var row = node.Id;
                foreach (var edge in node.Edges)
                {
                    var col = edge.ToId;
                    if (_G[row, col] > 0 && _G[row, col] != decimal.MaxValue && _G[row, col] != edge.Len)
                    {
                        throw new Exception(string.Format("边{0}-{1} 的数据有不一致的情况", row, col));
                    }
                    _G[row, col] = edge.Len;
                }
            }
            #endregion
        }
    }
}

            var nodes=new List<Dijkstra.N>();
            #region 构建Node列表
            var node0 = new Dijkstra.N(0);
            node0.Edges.Add(new Dijkstra.E(1, 4));
            node0.Edges.Add(new Dijkstra.E(7, 8));
            nodes.Add(node0);

            var node1 = new Dijkstra.N(1);
            node1.Edges.Add(new Dijkstra.E(0, 4));
            node1.Edges.Add(new Dijkstra.E(2, 8));
            node1.Edges.Add(new Dijkstra.E(7, 11));
            nodes.Add(node1);

            var node2 = new Dijkstra.N(2);
            node2.Edges.Add(new Dijkstra.E(1, 8));
            node2.Edges.Add(new Dijkstra.E(3, 7));
            node2.Edges.Add(new Dijkstra.E(8, 2));
            node2.Edges.Add(new Dijkstra.E(5, 4));
            nodes.Add(node2);

            var node3 = new Dijkstra.N(3);
            node3.Edges.Add(new Dijkstra.E(2, 7));
            node3.Edges.Add(new Dijkstra.E(4, 9));
            node3.Edges.Add(new Dijkstra.E(5, 14));
            nodes.Add(node3);

            var node4 = new Dijkstra.N(4);
            node4.Edges.Add(new Dijkstra.E(3, 9));
            node4.Edges.Add(new Dijkstra.E(5, 10));
            nodes.Add(node4);

            var node5 = new Dijkstra.N(5);
            node5.Edges.Add(new Dijkstra.E(3, 14));
            node5.Edges.Add(new Dijkstra.E(4, 10));
            node5.Edges.Add(new Dijkstra.E(2, 4));
            node5.Edges.Add(new Dijkstra.E(6, 2));
            nodes.Add(node5);

            var node6 = new Dijkstra.N(6);
            node6.Edges.Add(new Dijkstra.E(5, 2));
            node6.Edges.Add(new Dijkstra.E(7, 1));
            node6.Edges.Add(new Dijkstra.E(8, 6));
            nodes.Add(node6);

            var node7 = new Dijkstra.N(7);
            node7.Edges.Add(new Dijkstra.E(0, 8));
            node7.Edges.Add(new Dijkstra.E(1, 11));
            node7.Edges.Add(new Dijkstra.E(6, 1));
            node7.Edges.Add(new Dijkstra.E(8, 7));
            nodes.Add(node7);

            var node8 = new Dijkstra.N(8);
            node8.Edges.Add(new Dijkstra.E(2, 2));
            node8.Edges.Add(new Dijkstra.E(6, 6));
            node8.Edges.Add(new Dijkstra.E(7, 7));
            nodes.Add(node8);

            #endregion
            var srv = new Dijkstra();
            var list= srv.Calc(nodes, node5);
            foreach (var way in list)
            {
                Console.WriteLine(String.Format("{0}->{1},距离:{2},路径:{3}",way.StartId,way.EndId,way.Distance,way.Way));
            }