加载中...

第十七题 Dijkstra算法

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

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

一：概序

   从下图中我要寻找V0到V3的最短路径，你会发现通往他们的两点路径有很多：V0->V4->V3，V0->V1->V3，当然你会认为前者是你要找的最短

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

二：构建

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

1.边节点

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

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

  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(N2)。。。 

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Diagnostics;
  6. using System.Threading;
  7. using System.IO;
  8. using System.Threading.Tasks;
  9.  
  10. namespace ConsoleApplication2
  11. {
  12.     public class Program
  13.     {
  14.         public static void Main()
  15.         {
  16.             Dictionary<int, string> dic = new Dictionary<int, string>();
  17.  
  18.             MatrixGraph graph = new MatrixGraph();
  19.  
  20.             graph.Build();
  21.  
  22.             var result = graph.Dijkstra();
  23.  
  24.             Console.WriteLine("各节点的最短路径为:");
  25.  
  26.             foreach (var key in result.Keys)
  27.             {
  28.                 Console.WriteLine("{0}", string.Join("->", result[key].vertexs));
  29.             }
  30.  
  31.             Console.Read();
  32.         }
  33.     }
  34.  
  35.     #region 定义矩阵节点
  36.     /// <summary>
  37.     /// 定义矩阵节点
  38.     /// </summary>
  39.     public class MatrixGraph
  40.     {
  41.         Graph graph = new Graph();
  42.  
  43.         public class Graph
  44.         {
  45.             /// <summary>
  46.             /// 顶点信息
  47.             /// </summary>
  48.             public int[] vertexs;
  49.  
  50.             /// <summary>
  51.             /// 边的条数
  52.             /// </summary>
  53.             public int[,] edges;
  54.  
  55.             /// <summary>
  56.             /// 顶点个数
  57.             /// </summary>
  58.             public int vertexsNum;
  59.  
  60.             /// <summary>
  61.             /// 边的个数
  62.             /// </summary>
  63.             public int edgesNum;
  64.         }
  65.  
  66.         #region 矩阵的构建
  67.         /// <summary>
  68.         /// 矩阵的构建
  69.         /// </summary>
  70.         public void Build()
  71.         {
  72.             //顶点数
  73.             graph.vertexsNum = 5;
  74.  
  75.             //边数
  76.             graph.edgesNum = 6;
  77.  
  78.             graph.vertexs = new int[graph.vertexsNum];
  79.  
  80.             graph.edges = new int[graph.vertexsNum, graph.vertexsNum];
  81.  
  82.             //构建二维数组
  83.             for (int i = 0; i < graph.vertexsNum; i++)
  84.             {
  85.                 //顶点
  86.                 graph.vertexs[i] = i;
  87.  
  88.                 for (int j = 0; j < graph.vertexsNum; j++)
  89.                 {
  90.                     graph.edges[i, j] = int.MaxValue;
  91.                 }
  92.             }
  93.  
  94.             //定义 6 条边
  95.             graph.edges[0, 1] = graph.edges[1, 0] = 2;
  96.             graph.edges[0, 2] = graph.edges[2, 0] = 5;
  97.             graph.edges[0, 4] = graph.edges[4, 0] = 3;
  98.             graph.edges[1, 3] = graph.edges[3, 1] = 4;
  99.             graph.edges[2, 4] = graph.edges[4, 2] = 5;
  100.             graph.edges[3, 4] = graph.edges[4, 3] = 2;
  101.  
  102.         }
  103.         #endregion
  104.  
  105.         #region 边的信息
  106.         /// <summary>
  107.         /// 边的信息
  108.         /// </summary>
  109.         public class Edge
  110.         {
  111.             //开始边
  112.             public int startEdge;
  113.  
  114.             //结束边
  115.             public int endEdge;
  116.  
  117.             //权重
  118.             public int weight;
  119.  
  120.             //是否使用
  121.             public bool isUse;
  122.  
  123.             //累计顶点
  124.             public HashSet<int> vertexs = new HashSet<int>();
  125.         }
  126.         #endregion
  127.  
  128.         #region Dijkstra算法
  129.         /// <summary>
  130.         /// Dijkstra算法
  131.         /// </summary>
  132.         public Dictionary<int, Edge> Dijkstra()
  133.         {
  134.             //收集顶点的相邻边
  135.             Dictionary<int, Edge> dic_edges = new Dictionary<int, Edge>();
  136.  
  137.             //weight=MaxValue:标识没有边
  138.             for (int i = 0; i < graph.vertexsNum; i++)
  139.             {
  140.                 //起始边
  141.                 var startEdge = i;
  142.  
  143.                 dic_edges.Add(startEdge, new Edge() { weight = int.MaxValue });
  144.             }
  145.  
  146.             //取第一个顶点
  147.             var start = 0;
  148.  
  149.             for (int i = 0; i < graph.vertexsNum; i++)
  150.             {
  151.                 //标记该顶点已经使用过
  152.                 dic_edges[start].isUse = true;
  153.  
  154.                 for (int j = 1; j < graph.vertexsNum; j++)
  155.                 {
  156.                     var end = j;
  157.  
  158.                     //取到相邻边的权重
  159.                     var weight = graph.edges[start, end];
  160.  
  161.                     //赋较小的权重
  162.                     if (weight < dic_edges[end].weight)
  163.                     {
  164.                         //与上一个顶点的权值累加
  165.                         var totalweight = dic_edges[start].weight == int.MaxValue ? weight : dic_edges[start].weight + weight;
  166.  
  167.                         if (totalweight < dic_edges[end].weight)
  168.                         {
  169.                             //将该顶点的相邻边加入到集合中
  170.                             dic_edges[end] = new Edge()
  171.                             {
  172.                                 startEdge = start,
  173.                                 endEdge = end,
  174.                                 weight = totalweight
  175.                             };
  176.  
  177.                             //将上一个边的节点的vertex累加
  178.                             dic_edges[end].vertexs = new HashSet<int>(dic_edges[start].vertexs);
  179.  
  180.                             dic_edges[end].vertexs.Add(start);
  181.                             dic_edges[end].vertexs.Add(end);
  182.                         }
  183.                     }
  184.                 }
  185.  
  186.                 var min = int.MaxValue;
  187.  
  188.                 //下一个进行比较的顶点
  189.                 int minkey = 0;
  190.  
  191.                 //取start邻接边中的最小值
  192.                 foreach (var key in dic_edges.Keys)
  193.                 {
  194.                     //取当前 最小的 key(使用过的除外)
  195.                     if (min > dic_edges[key].weight && !dic_edges[key].isUse)
  196.                     {
  197.                         min = dic_edges[key].weight;
  198.                         minkey = key;
  199.                     }
  200.                 }
  201.  
  202.                 //从邻接边的顶点再开始找
  203.                 start = minkey;
  204.             }
  205.  
  206.             return dic_edges;
  207.         }
  208.         #endregion
  209.     }
  210.     #endregion
  211. }

还没有评论.