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 那样做图吗？用大数据的软件做这种图，有点蠢的。

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 Club，SwiftStructures。

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

1D Array

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

比如这么一个 2D array：

我们取它的上半部分来操作。在 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 > v 和 else 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 的高清图：