对dijkstra算法的自我理解，c#例子

dijkstra该算法主要应用在求解最短路径，从最近点开始，广度搜索。

假设有向图中有10个顶点，求其中某个顶点a到其它顶点的最短路径。。满足贪心算法的2个标准。时间复杂度为O(N2)

此问题可以进行分解。某个顶点a到到其他顶点c必定是从a直接到c 或者是从a到离a最近的顶点b，再到c。

算法思想：

初始化：

d[] 已计算顶点集合初始为原点a

s[] 待计算顶点集合初始为除了a外其他顶点

minlen[] 每次找到的最近点与其它点s[]的距离

过程：

从a点开始，遍历与其他顶点（s[]）的距离minlen[]。找到距离a点最近的顶点（x）把x加到d[]中，s[]中减去，并更新minlen[]中距离

重复这个过程。

所以是两个for循环嵌套，时间复杂度为O（n2）

参照百度cijkstra java写的代码，看到很少有c#的，就写了个。

   static void Main(string[] args)

         {

             double[,] path = getpath();//随机生成10个点之间的距离矩阵

             Dictionary<int, double> result = getr(path);//result<点，距离>

         }

         public static Dictionary<int, double> getr(double[,] da)

         {

             Dictionary<int, double> result = new Dictionary<int, double>();

             result.Add(, ); //默认添加首点

             int n =Convert.ToInt32(Math.Sqrt(da.Length));

             double[] minlen =new double[n];//存储每次找到的最近点距离其它点的距离

             int[] visit =new int[n]; //一共0到9点 计算过后的点为1

             for(int i=;i<n;i++){

                 minlen[i] = da[, i];//初始化首点与其它点距离

             }

             visit[] = ; //默认第一点为原点,已经添加到visit集合

             int minj = ; //遍历循环默认第一点最小

             for (int i = ; i < n; i++) {

                 double min = double.PositiveInfinity;

                 for (int j =; j < n ; j++) {

                     if (visit[j] ==  && minlen[j] < min) {//遍历minlen 找到最小

                         min = minlen[j];//j循环最小值

                         minj = j; //第minj最小

                     }

                 }

                 if (min == double.PositiveInfinity) return result;//测试数据有可能出现x点到其它点没有距离

                 visit[minj] = ; //第minj点已添加

                 result.Add(minj,min);

                 for (int j = ; j < n ; j++)//重新计算minlen

                 {

                     if (visit[j] ==  && minlen[minj] !=double.PositiveInfinity

                             && da[minj,j] != double.PositiveInfinity

                             && minlen[j] > (minlen[minj] + da[minj,j]))

                     {

                         minlen[j] = minlen[minj] + da[minj,j];

                     }

                 }

             }

             return result;

         }

         public static double[,] getpath(int num) {

              Random rd=new Random();

             double[,] path = new double[num, num];

             for (int i = ; i < num; i++)

             {

                 for (int j = ; j < num; j++)

                 {

                     path[i, j] = rd.Next(,);//生成测试数据

                     if (path[i, j] >  || i == j) path[i, j] = double.PositiveInfinity;

                 }

             }

             return path;

         }

巴特西

对dijkstra算法的自我理解，c#例子

最新文章

热门文章