神刀安全网

Dijkstra 和 Floyd 装甲进化

关于“你们的”十一

关于你们的十一,反正我是睁一只眼闭一只眼,我没看见好吧。看着朋友圈里的小伙伴各种秀美食,秀美景,秀自己的狗有多蠢,特别是国内的同学朋友,不管上不上班,反正这个假他们肯定是放的。而我却在图书馆的角落默默地写着算法作业。一个为期2周的小 project,看题目也知道了,就俩简单的算法,网上也有很多相关的教程,那我为什么还要写这篇文章呢?

首先,我写的是“装甲”进化版的 Dijkstra & Floyd。用的是 Swift(虽然教授不厌其烦的说 C 是最好的学算法的语言),我本科 CS 用的 C++,实在是不喜欢 C++。我先介绍一下教授的要求吧。

要求太长了,想看一看的点这里,我简化一下:

  • 2 个算法,Dijkstra 和 Floyd 最短路径算法
  • 3 种数据结构,2D Array, 1D Array, Linked List
  • 2 种 Test cases, 一种 Complete Graph, 一种 Sparse Graph
  • 12 张图,对应上面的 2*3*2=12 个程序的时间复杂度

我上课听到这个要求后的第一反应是我要做一个 iOS App。教授是要我们 plot 出 12 张图,我如果不用 iOS 作图,难道还要用 R 像我们上 Machine Learning 那样做图吗?用大数据的软件做这种图,有点蠢的。

Dijkstra 和 Floyd 装甲进化
Paste_Image.png

BTW, 文章同步更新在我的博客,欢迎访问。

2 个算法,3 个数据结构

关于这两个算法的思路,与 2D array 和 Linked list 版本的教程,我强烈推荐 Geeksforgeeks,这是 2D array 版本的,这是 Linked List 版本的;Floyd 的呢,网上我只找到了 2D array 版本的。那 1D 和 Linked list 怎么办呢?如果你也是喜欢 Swift, 想用学一些 Swift 的数据结构和算法,我强烈推荐这两个网站:Swift Algorithm ClubSwiftStructures

我在这里就讲一讲上面提供的教程里没有的几个程序吧,1D 的 Dijkstra,1DLinked list 的 Floyd。

1D Array

1D 的原因是因为有时候我们的数据会非常大,如果只存取/操作一半的数据,会节省很多的时间和空间。所以这里 1D 的主要思路就是如何将 2D 的数据 map 到 1D 上面。

比如这么一个 2D array:

Dijkstra 和 Floyd 装甲进化

我们取它的上半部分来操作。在 2D 中 0 行 4 列的数是 6,那么在 1D 中 6 是第几个?是第 3 个(所有 index 都从 0 开始),就有 (0, 4) -> 3,再来一组,第 1 行 2 列的 3,在 1D 中是第 4 个,(1, 2) -> 4。如此计算出 (i, j) -> x,这个 x 是多少?如果数组共有 n 行 n 列,那么 x = (2n - 1- i)*i/2 + j - i - 1。这是求解 1D array 的 Dijkstra 和 Floyd 的关键。我们这次用的是无向图,所以对应的还有 (2*n-1-j)*j/2+i-j-1,判断条件就是 i < j 还是 i > j

我用 Dijkstra 的代码来说明:

func dijkstra1D(_ graph: [Int], _ src: Int) {     let V = Int(sqrt(Double(2 * graph.count))) + 1     var dist = Array(repeating: Int.max, count: V)     var sptSet = Array(repeating: false, count: V)     dist[src] = 0     for _ in 0..<V-1     {         let u = minDistance(dist, sptSet, V)         sptSet[u] = true         for v in 0..<V {             let index = (2*V - 1 - u)*u/2+v-u-1             let temp = (2*V - 1 - v)*v/2+u-v-1             if sptSet[v] == false && dist[u] != Int.max && dist[u] + graph[index] < dist[v] {                 if u > v {                     if graph[temp] > 0 && dist[u] + graph[temp] < dist[v] {                         dist[v] = dist[u] + graph[temp]                     }                 } else if u < v {                     if graph[index] > 0 {                         dist[v] = dist[u] + graph[index]                     }                 }             }         }     } //    print4(dist, V) }

中间的 if u > velse if u < v 里面的就是我上面说到的关键部分了。

Linked List

Dijkstra 的 Linked List 版本上面已经提供了教程了,应该没人比 geeksforgeeks 写的更好了。。我这里稍微讲一下 Floyd 版本的。因为 Floyd 的算法思路还是比较简单的,关键是要遍历很多次整个图,因为 2D 里面它就有 3 个循环。我是弄了个数组,把链表转成了 2D 的来解决了,好像这样不太好,因为这样的话链表的存储优势就完全没了,到最后还是转成了 2D 来做。但用我们教授的话来说就是,每个程序的实现都要按照要求来做,要求不同,实现也会有不同。。。这里我们教授的 input 输入没有很复杂,所以专成 2D 完全可以 😄 下面就是代码的主要部分。

var dist = Array(repeating: Array(repeatElement(Int(Int32.max), count: V)), count: V)     var mark = Array(repeating: false, count: V)     var u = 0, v = 0     for i in 0..<V {         var cur = graph.array[i].head         u = i         mark[u] = true         while cur != nil {             v = cur!.dest             if mark[v] == false {                 dist[u][v] = cur!.weight                 dist[v][u] = cur!.weight             }             cur = cur?.next         }     }

2 种类型的图

Complete Graph 用教授的话定义就是:

a graph with a link between every pair of nodes

而 Sparse 呢:

a graph with exactly n-1 links

生成这两种图的时候,我们需要生成对应于 2D, 1D 和 linked list 版本的,所以会有 6 个 function。程序有点长,就不放上来了。讲几个注意点,因为是无向图,所以都要注意两边的三角区域都要赋值,比如这个 complete graph 的:

completeGraph[i][j] = rand completeGraph[j][i] = rand

生成 sparse graph 的时候,我们画一下图就可以知道,从 0 开始,随机选出下一个点,假如是 4*4 的表格,下个点是 3,那么我们再选下个点的时候,需要从 1 和 2 中选,这里我们需要一个类似于 chosenNodes 的标记,如果随机到的是已经选过的,我们有两种方法,一种是在随即一遍,还有一种是取模,很明显取模会快很多,特别是剩下的数不多的时候。下面是生成 sparse graph 的函数:

func sparse(_ n: Int) -> [[Int]]     {         var sparseGraph = Array(repeating: Array(repeatElement(0, count: n)), count:n)         var chosenNodes = Array(repeating: false, count: n)         var i = 0         while chosenNodes.contains(false) {             chosenNodes[i] = true             if chosenNodes.contains(false) {                 var pickJ = Int(arc4random_uniform(UInt32(n)))                 if chosenNodes[pickJ] == true {                     while chosenNodes[pickJ] == true {                         pickJ = (pickJ + 1)%(n)                     }                 }                 let j = pickJ                 let rand = Int(arc4random_uniform(UInt32(n))) + 1                 sparseGraph[i][j] = rand                 sparseGraph[j][i] = rand                 i = j             }         }         return sparseGraph     }

基于链表的图的生成很简单,只要根据循环用几次 addEdge() 就可以了。

使用 Charts 作图

关于如何使用 Charts,这里有一篇很好的教程,因为他是在 swift 3 之前写的,所以语法有点小错误,有疑问的可以看看我的 project,当然最权威的还是官方的 github

如您在上面所看到的,我做的是 Complete graph 和 Sparse graph 两种分开的折线图,比较各算法在同样的图上的速度。我本来想过很多种分类作图的方式,感觉还是这样比较直观。gif 试了好几遍没放上来,只好放图了,下面放一张 sparse 的高清图:

Dijkstra 和 Floyd 装甲进化
Paste_Image.png

如果喜欢我的分享,请点赞💗和关注,也可以 tip 一波安抚一下国庆敲代码的心。

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Dijkstra 和 Floyd 装甲进化

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址