• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Dijkstra算法(Swift版)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

原理

我们知道,使用Breadth-first search算法能够找到到达某个目标的最短路径,但这个算法没考虑weight,因此我们再为每个edge添加了权重后,我们就需要使用Dijkstra算法来寻找权重和最小的路径。

其实原理很简单,我们最终的目的是计算出每一个节点到起点的权重之和,同时获取得到这个权重和的路径数组。
那么权重和最小的那个自然就是我们要的结果。

在该算法中有一下几个核心的思想:

  • 当我们遍历到某个节点时,计算出该节点到起点的权重和之后=,该节点就不在使用了,或删除或者标记为已检阅
  • 当该节点的某个neighbor节点加上权重的值小于该neighbor节点时,跟新该neighbor节点的数据

实现这个算法的方式有多种,在该文章中,我们把某些数据直接封装到了节点中。

Vertex

Vertex.swift

import Foundation

open class Vertex {

    open var identifier: String
    open var neighbors: [(Vertex, Double)] = []
    open var pathLengthFromStart = Double.infinity
    open var pathVerticesFromStart: [Vertex] = []

    public init(identifier: String) {
        self.identifier = identifier
    }

    open func clearCache() {
        pathLengthFromStart = Double.infinity
        pathVerticesFromStart = []
    }
}

extension Vertex: Hashable {
    open var hashValue: Int {
        return identifier.hashValue
    }
}

extension Vertex: Equatable {
    public static func ==(lhs: Vertex, rhs: Vertex) -> Bool {
        return lhs.hashValue == rhs.hashValue
    }
}

Dijkstra

Dijkstra.swift

import Foundation

public class Dijkstra {
    private var totalVertices: Set<Vertex>

    public init(vertices: Set<Vertex>) {
        totalVertices = vertices
    }

    private func clearCache() {
        totalVertices.forEach { $0.clearCache() }
    }

    public func findShortestPaths(from startVertex: Vertex) {
        clearCache()
        var currentVertices = self.totalVertices
        startVertex.pathLengthFromStart = 0
        startVertex.pathVerticesFromStart.append(startVertex)
        var currentVertex: Vertex? = startVertex
        while let vertex = currentVertex {
            currentVertices.remove(vertex)
            let filteredNeighbors = vertex.neighbors.filter { currentVertices.contains($0.0) }
            for neighbor in filteredNeighbors {
                let neighborVertex = neighbor.0
                let weight = neighbor.1

                let theoreticNewWeight = vertex.pathLengthFromStart + weight
                if theoreticNewWeight < neighborVertex.pathLengthFromStart {
                    neighborVertex.pathLengthFromStart = theoreticNewWeight
                    neighborVertex.pathVerticesFromStart = vertex.pathVerticesFromStart
                    neighborVertex.pathVerticesFromStart.append(neighborVertex)
                }
            }
            if currentVertices.isEmpty {
                currentVertex = nil
                break
            }
            currentVertex = currentVertices.min { $0.pathLengthFromStart < $1.pathLengthFromStart }
        }
    }
}

演示

我们就演示这个例子

//: Playground - noun: a place where people can play
import Foundation

// last checked with Xcode 9.0b4
#if swift(>=4.0)
print("Hello, Swift 4!")
#endif

var vertices: Set<Vertex> = Set()

/// Create vertexs
var vertexA = Vertex(identifier: "A")
var vertexB = Vertex(identifier: "B")
var vertexC = Vertex(identifier: "C")
var vertexD = Vertex(identifier: "D")
var vertexE = Vertex(identifier: "E")
var vertexF = Vertex(identifier: "F")

/// Setting neighbors
vertexA.neighbors.append(contentsOf: [(vertexB, 5), (vertexD, 2)])
vertexB.neighbors.append(contentsOf: [(vertexC, 4), (vertexE, 2)])
vertexC.neighbors.append(contentsOf: [(vertexE, 6), (vertexF, 3)])
vertexD.neighbors.append(contentsOf: [(vertexB, 8), (vertexE, 7)])
vertexE.neighbors.append(contentsOf: [(vertexF, 1)])

vertices.insert(vertexA)
vertices.insert(vertexB)
vertices.insert(vertexC)
vertices.insert(vertexD)
vertices.insert(vertexE)
vertices.insert(vertexF)


let dijkstra = Dijkstra(vertices: vertices)
dijkstra.findShortestPaths(from: vertexA)

for vertex in vertices {
    let paths = vertex.pathVerticesFromStart.map({ $0.identifier })
    print("(A=>" + vertex.identifier + "): " + paths.joined(separator: " -> "))
}

打印结果:

(A=>B): A -> B
(A=>A): A
(A=>F): A -> B -> E -> F
(A=>C): A -> B -> C
(A=>D): A -> D
(A=>E): A -> B -> E

主要代码来自于Dijkstra


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift 之 泛型 与 访问控制发布时间:2022-07-14
下一篇:
面向不同需求的对象存储系统对比:Ceph与Swift发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap