经典算法题每日演练——第十七题 Dijkstra算法

原文:经典算法题每日演练——第十七题 Dijkstra算法

 

      或许在生活中，经常会碰到针对某一个问题，在众多的限制条件下，如何去寻找一个最优解？可能大家想到了很多诸如“线性规划”，“动态规划”

这些经典策略，当然有的问题我们可以用贪心来寻求整体最优解，在图论中一个典型的贪心法求最优解的例子就莫过于“最短路径”的问题。

一：概序

   从下图中我要寻找V₀到V₃的最短路径，你会发现通往他们的两点路径有很多：V₀->V₄->V₃，V₀->V₁->V_3，当然你会认为前者是你要找的最短

路径，那如果说图的顶点非常多，你还会这么轻易的找到吗？下面我们就要将刚才我们那点贪心的思维系统的整理下。

二：构建

    如果大家已经了解Prim算法，那么Dijkstra算法只是在它的上面延伸了下，其实也是很简单的。

1.边节点

  这里有点不一样的地方就是我在边上面定义一个vertexs来记录贪心搜索到某一个节点时曾经走过的节点，比如从V₀贪心搜索到V₃时，我们V₃

的vertexs可能存放着V₀,V₄,V₃这些曾今走过的节点，或许最后这三个节点就是我们要寻找的最短路径。

 1 #region 边的信息
 2         /// <summary>
 3         /// 边的信息
 4         /// </summary>
 5         public class Edge
 6         {
 7             //开始边
 8             public int startEdge;
 9
10             //结束边
11             public int endEdge;
12
13             //权重
14             public int weight;
15
16             //是否使用
17             public bool isUse;
18
19             //累计顶点
20             public HashSet<int> vertexs = new HashSet<int>();
21         }
22         #endregion

2.Dijkstra算法

首先我们分析下Dijkstra算法的步骤：

有集合M={V0,V1,V2,V3,V4}这样5个元素，我们用

TempVertex表示该顶点是否使用。

Weight表示该Path的权重(默认都为MaxValue)。

Path表示该顶点的总权重。

①. 从集合M中挑选顶点V0为起始点。给V0的所有邻接点赋值，要赋值的前提是要赋值的weight要小于原始的weight，并且排除已经访问过

     的顶点，然后挑选当前最小的weight作为下一次贪心搜索的起点，就这样V0V1为挑选为最短路径，如图2。

②. 我们继续从V1这个顶点开始给邻接点以同样的方式赋值，最后我们发现V0V4为最短路径。也就是图3。

。。。

③. 最后所有顶点的最短路径就这样求出来了 。

 1 #region Dijkstra算法
 2         /// <summary>
 3         /// Dijkstra算法
 4         /// </summary>
 5         public Dictionary<int, Edge> Dijkstra()
 6         {
 7             //收集顶点的相邻边
 8             Dictionary<int, Edge> dic_edges = new Dictionary<int, Edge>();
 9
10             //weight=MaxValue:标识没有边
11             for (int i = 0; i < graph.vertexsNum; i++)
12             {
13                 //起始边
14                 var startEdge = i;
15
16                 dic_edges.Add(startEdge, new Edge() { weight = int.MaxValue });
17             }
18
19             //取第一个顶点
20             var start = 0;
21
22             for (int i = 0; i < graph.vertexsNum; i++)
23             {
24                 //标记该顶点已经使用过
25                 dic_edges[start].isUse = true;
26
27                 for (int j = 1; j < graph.vertexsNum; j++)
28                 {
29                     var end = j;
30
31                     //取到相邻边的权重
32                     var weight = graph.edges[start, end];
33
34                     //赋较小的权重
35                     if (weight < dic_edges[end].weight)
36                     {
37                         //与上一个顶点的权值累加
38                         var totalweight = dic_edges[start].weight == int.MaxValue ? weight : dic_edges[start].weight + weight;
39
40                         if (totalweight < dic_edges[end].weight)
41                         {
42                             //将该顶点的相邻边加入到集合中
43                             dic_edges[end] = new Edge()
44                             {
45                                 startEdge = start,
46                                 endEdge = end,
47                                 weight = totalweight
48                             };
49
50                             //将上一个边的节点的vertex累加
51                             dic_edges[end].vertexs = new HashSet<int>(dic_edges[start].vertexs);
52
53                             dic_edges[end].vertexs.Add(start);
54                             dic_edges[end].vertexs.Add(end);
55                         }
56                     }
57                 }
58
59                 var min = int.MaxValue;
60
61                 //下一个进行比较的顶点
62                 int minkey = 0;
63
64                 //取start邻接边中的最小值
65                 foreach (var key in dic_edges.Keys)
66                 {
67                     //取当前 最小的 key(使用过的除外)
68                     if (min > dic_edges[key].weight && !dic_edges[key].isUse)
69                     {
70                         min = dic_edges[key].weight;
71                         minkey = key;
72                     }
73                 }
74
75                 //从邻接边的顶点再开始找
76                 start = minkey;
77             }
78
79             return dic_edges;
80         }
81         #endregion

总的代码：复杂度很烂O(N²)。。。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;
using System.Threading.Tasks;

namespace ConsoleApplication2
{
    public class Program
    {
        public static void Main()
        {
            Dictionary<int, string> dic = new Dictionary<int, string>();

            MatrixGraph graph = new MatrixGraph();

            graph.Build();

            var result = graph.Dijkstra();

            Console.WriteLine("各节点的最短路径为:");

            foreach (var key in result.Keys)
            {
                Console.WriteLine("{0}", string.Join("->", result[key].vertexs));
            }

            Console.Read();
        }
    }

    #region 定义矩阵节点
    /// <summary>
    /// 定义矩阵节点
    /// </summary>
    public class MatrixGraph
    {
        Graph graph = new Graph();

        public class Graph
        {
            /// <summary>
            /// 顶点信息
            /// </summary>
            public int[] vertexs;

            /// <summary>
            /// 边的条数
            /// </summary>
            public int[,] edges;

            /// <summary>
            /// 顶点个数
            /// </summary>
            public int vertexsNum;

            /// <summary>
            /// 边的个数
            /// </summary>
            public int edgesNum;
        }

        #region 矩阵的构建
        /// <summary>
        /// 矩阵的构建
        /// </summary>
        public void Build()
        {
            //顶点数
            graph.vertexsNum = 5;

            //边数
            graph.edgesNum = 6;

            graph.vertexs = new int[graph.vertexsNum];

            graph.edges = new int[graph.vertexsNum, graph.vertexsNum];

            //构建二维数组
            for (int i = 0; i < graph.vertexsNum; i++)
            {
                //顶点
                graph.vertexs[i] = i;

                for (int j = 0; j < graph.vertexsNum; j++)
                {
                    graph.edges[i, j] = int.MaxValue;
                }
            }

            //定义 6 条边
            graph.edges[0, 1] = graph.edges[1, 0] = 2;
            graph.edges[0, 2] = graph.edges[2, 0] = 5;
            graph.edges[0, 4] = graph.edges[4, 0] = 3;
            graph.edges[1, 3] = graph.edges[3, 1] = 4;
            graph.edges[2, 4] = graph.edges[4, 2] = 5;
            graph.edges[3, 4] = graph.edges[4, 3] = 2;

        }
        #endregion

        #region 边的信息
        /// <summary>
        /// 边的信息
        /// </summary>
        public class Edge
        {
            //开始边
            public int startEdge;

            //结束边
            public int endEdge;

            //权重
            public int weight;

            //是否使用
            public bool isUse;

            //累计顶点
            public HashSet<int> vertexs = new HashSet<int>();
        }
        #endregion

        #region Dijkstra算法
        /// <summary>
        /// Dijkstra算法
        /// </summary>
        public Dictionary<int, Edge> Dijkstra()
        {
            //收集顶点的相邻边
            Dictionary<int, Edge> dic_edges = new Dictionary<int, Edge>();

            //weight=MaxValue:标识没有边
            for (int i = 0; i < graph.vertexsNum; i++)
            {
                //起始边
                var startEdge = i;

                dic_edges.Add(startEdge, new Edge() { weight = int.MaxValue });
            }

            //取第一个顶点
            var start = 0;

            for (int i = 0; i < graph.vertexsNum; i++)
            {
                //标记该顶点已经使用过
                dic_edges[start].isUse = true;

                for (int j = 1; j < graph.vertexsNum; j++)
                {
                    var end = j;

                    //取到相邻边的权重
                    var weight = graph.edges[start, end];

                    //赋较小的权重
                    if (weight < dic_edges[end].weight)
                    {
                        //与上一个顶点的权值累加
                        var totalweight = dic_edges[start].weight == int.MaxValue ? weight : dic_edges[start].weight + weight;

                        if (totalweight < dic_edges[end].weight)
                        {
                            //将该顶点的相邻边加入到集合中
                            dic_edges[end] = new Edge()
                            {
                                startEdge = start,
                                endEdge = end,
                                weight = totalweight
                            };

                            //将上一个边的节点的vertex累加
                            dic_edges[end].vertexs = new HashSet<int>(dic_edges[start].vertexs);

                            dic_edges[end].vertexs.Add(start);
                            dic_edges[end].vertexs.Add(end);
                        }
                    }
                }

                var min = int.MaxValue;

                //下一个进行比较的顶点
                int minkey = 0;

                //取start邻接边中的最小值
                foreach (var key in dic_edges.Keys)
                {
                    //取当前 最小的 key(使用过的除外)
                    if (min > dic_edges[key].weight && !dic_edges[key].isUse)
                    {
                        min = dic_edges[key].weight;
                        minkey = key;
                    }
                }

                //从邻接边的顶点再开始找
                start = minkey;
            }

            return dic_edges;
        }
        #endregion
    }
    #endregion
}