しめ鯖日記

swift, iPhoneアプリ開発, ruby on rails等のTipsや入門記事書いてます

ダイクストラ法で最短経路を求めてみる

ダイクストラ法という最短経路を求めるアルゴリズムをSwiftで試してみました。
参考にさせて頂いたのはこちらの記事です。

ダイクストラ法(最短経路問題)

ダイクストラ法とは

ダイクストラ法(だいくすとらほう、英: Dijkstra’s algorithm)はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。

Wikipediaによると上記のようなものになります。

ダイクストラ法 - Wikipedia

今回はこれをSwiftで実装してみます。

実装

まずは画面上に点を設置します。

import UIKit

class ViewController: UIViewController {
    override func viewDidLoad() {
        super.viewDidLoad()
        
        (0...5).forEach { _ in
            let dot = UIView(frame: CGRect(
                x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))),
                y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))),
                width: 20, height: 20))
            dot.backgroundColor = UIColor.darkGray
            dot.layer.cornerRadius = dot.frame.width / 2
            view.addSubview(dot)
        }
    }
}

f:id:llcc:20170519000635p:plain

次にStartとGoalを決めます。

class ViewController: UIViewController {
    override func viewDidLoad() {
        super.viewDidLoad()
        
        var dots: [UIView] = []
        (0...5).forEach { _ in
            let dot = UIView(frame: CGRect(
                x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))),
                y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))),
                width: 20, height: 20))
            dot.backgroundColor = UIColor.darkGray
            dot.layer.cornerRadius = dot.frame.width / 2
            dots.append(dot)
            view.addSubview(dot)
        }
        
        let startLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20))
        startLabel.text = "S"
        startLabel.textColor = UIColor.white
        startLabel.textAlignment = .center
        dots.first?.addSubview(startLabel)
        let goalLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20))
        goalLabel.text = "G"
        goalLabel.textColor = UIColor.white
        goalLabel.textAlignment = .center
        dots.last?.addSubview(goalLabel)
    }
}

f:id:llcc:20170519002227p:plain

続けて線同士を繋げて経路を作ろうと思います。

各点に他経路への参照を持たせるためにDotViewというクラスを作って各点をUIViewからDotViewにします。
下だと場合によっては循環参照が起こったり場合によってゴールまで着けない事もあるのですが、今回は「ダイクストラ法」の勉強という事で無視します。

import UIKit

class ViewController: UIViewController {
    override func viewDidLoad() {
        super.viewDidLoad()
        
        var dots: [DotView] = [] // UIViewをDotViewに変更
        (0...5).forEach { _ in
            let dot = DotView(frame: CGRect( // UIViewをDotViewに変更
                x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))),
                y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))),
                width: 20, height: 20))
            dot.backgroundColor = UIColor.darkGray
            dot.layer.cornerRadius = dot.frame.width / 2
            dots.append(dot)
            view.addSubview(dot)
        }
        
        let startLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20))
        startLabel.text = "S"
        startLabel.textColor = UIColor.white
        startLabel.textAlignment = .center
        dots.first?.addSubview(startLabel)
        let goalLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20))
        goalLabel.text = "G"
        goalLabel.textColor = UIColor.white
        goalLabel.textAlignment = .center
        dots.last?.addSubview(goalLabel)
        
        // 以下今回追加
        dots.forEach { dot in
            var otherDots = dots.filter { $0 != dot }
            dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count)))))
            dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count)))))
        }
    }
}

// 以下が今回追加分
class DotView: UIView {
    var otherDots: [UIView] = []
}

上で参照を持たせたので、次は線を引きます。

import UIKit

class ViewController: UIViewController {
    override func viewDidLoad() {
        super.viewDidLoad()
        
        var dots: [DotView] = []
        (0...5).forEach { _ in
            let dot = DotView(frame: CGRect(
                x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))),
                y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))),
                width: 20, height: 20))
            dot.backgroundColor = UIColor.darkGray
            dot.layer.cornerRadius = dot.frame.width / 2
            dots.append(dot)
            view.addSubview(dot)
        }
        
        let startLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20))
        startLabel.text = "S"
        startLabel.textColor = UIColor.white
        startLabel.textAlignment = .center
        dots.first?.addSubview(startLabel)
        let goalLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20))
        goalLabel.text = "G"
        goalLabel.textColor = UIColor.white
        goalLabel.textAlignment = .center
        dots.last?.addSubview(goalLabel)
        
        dots.forEach { dot in
            var otherDots = dots.filter { $0 != dot }
            dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count)))))
            dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count)))))
        }
        // 以下は今回追加
        dots.forEach { dot in
            dot.otherDots.forEach { otherDot in
                let lineView = LineView(start: dot.frame.origin, end: otherDot.frame.origin)
                view.addSubview(lineView)
                view.sendSubview(toBack: lineView)
            }
        }
    }
}

class DotView: UIView {
    var otherDots: [DotView] = []
}

// 以下は今回追加
class LineView: UIView {
    let start: CGPoint
    let end: CGPoint
    
    init(start: CGPoint, end: CGPoint) {
        self.start = start
        self.end   = end
        
        super.init(frame: CGRect(
            x: ([start.x, end.x].min() ?? 0) + 10,
            y: ([start.y, end.y].min() ?? 0) + 10,
            width: abs(start.x - end.x),
            height: abs(start.y - end.y)))
        
        backgroundColor = UIColor.clear
    }
    
    required init?(coder aDecoder: NSCoder) {
        fatalError("init(coder:) has not been implemented")
    }
    
    override func draw(_ rect: CGRect) {
        let path = UIBezierPath()
        path.move(to: CGPoint(x: start.x - frame.origin.x + 10, y: start.y - frame.origin.y + 10))
        path.addLine(to: CGPoint(x: end.x - frame.origin.x + 10, y: end.y - frame.origin.y + 10))
        path.lineWidth = 4.0
        UIColor.darkGray.setStroke()
        path.stroke()
    }
}

これで経路を作る事ができました。

f:id:llcc:20170520130216p:plain

ここからダイクストラ法を実装していきます。
まずはDotViewにtypeとscore(スタートからの距離)を追加して、viewDidLoadの中でtypeを設定します。

import UIKit

class ViewController: UIViewController {
    override func viewDidLoad() {
        super.viewDidLoad()
        
        var dots: [DotView] = []
        (0...5).forEach { _ in
            let dot = DotView(frame: CGRect(
                x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))),
                y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))),
                width: 20, height: 20))
            dot.backgroundColor = UIColor.darkGray
            dot.layer.cornerRadius = dot.frame.width / 2
            dots.append(dot)
            view.addSubview(dot)
        }
        
        let startLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20))
        startLabel.text = "S"
        startLabel.textColor = UIColor.white
        startLabel.textAlignment = .center
        dots.first?.addSubview(startLabel)
        dots.first?.type = .start // 追加
        let goalLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20))
        goalLabel.text = "G"
        goalLabel.textColor = UIColor.white
        goalLabel.textAlignment = .center
        dots.last?.addSubview(goalLabel)
        dots.last?.type = .goal // 追加
        
        dots.forEach { dot in
            var otherDots = dots.filter { $0 != dot }
            dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count)))))
            dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count)))))
        }
        dots.forEach { dot in
            dot.otherDots.forEach { otherDot in
                let lineView = LineView(start: dot.frame.origin, end: otherDot.frame.origin)
                view.addSubview(lineView)
                view.sendSubview(toBack: lineView)
            }
        }
    }
}

// 今回修正
class DotView: UIView {
    enum DotType {
        case start
        case goal
        case normal
    }
    
    var otherDots: [DotView] = []
    var score: CGFloat = 0
    var type: DotType = .normal
    var routeDots: [DotView] = []
}

// 省略

経路を作ったので、どれが最短経路かを計算します。
ViewControllerを以下のように修正します。

import UIKit

class ViewController: UIViewController {
    override func viewDidLoad() {
        super.viewDidLoad()
        
        var dots: [DotView] = []
        (0...5).forEach { _ in
            let dot = DotView(frame: CGRect(
                x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))),
                y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))),
                width: 20, height: 20))
            dot.backgroundColor = UIColor.darkGray
            dot.layer.cornerRadius = dot.frame.width / 2
            dots.append(dot)
            view.addSubview(dot)
        }
        
        let startLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20))
        startLabel.text = "S"
        startLabel.textColor = UIColor.white
        startLabel.textAlignment = .center
        dots.first?.addSubview(startLabel)
        dots.first?.type = .start
        let goalLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20))
        goalLabel.text = "G"
        goalLabel.textColor = UIColor.white
        goalLabel.textAlignment = .center
        dots.last?.addSubview(goalLabel)
        dots.last?.type = .goal
        
        dots.forEach { dot in
            var otherDots = dots.filter { $0 != dot }
            dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count)))))
            dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count)))))
        }
        dots.forEach { dot in
            dot.otherDots.forEach { otherDot in
                let lineView = LineView(start: dot.frame.origin, end: otherDot.frame.origin)
                view.addSubview(lineView)
                view.sendSubview(toBack: lineView)
            }
        }
        
        if let start = dots.first {
            var targetDots = [start]
            while targetDots.count != 0 {
                let targetDot = targetDots.remove(at: 0)
                targetDot.otherDots.forEach {
                    let dx = targetDot.frame.origin.x - $0.frame.origin.x
                    let dy = targetDot.frame.origin.y - $0.frame.origin.y
                    if $0.score == 0 || targetDot.score + sqrt(dx*dx + dy*dy) < $0.score {
                        $0.score = targetDot.score + sqrt(dx*dx + dy*dy)
                        targetDots.append($0)
                        $0.routeDots = targetDot.routeDots + [targetDot]
                    }
                }
            }
        }
        if let last = dots.last, last.routeDots.count != 0 {
            last.routeDots.append(last)
            (0...(last.routeDots.count - 2)).forEach {
                let lineView = LineView(
                    start: last.routeDots[$0].frame.origin,
                    end: last.routeDots[$0 + 1].frame.origin,
                    color: UIColor.red,
                    lineWidth: 2)
                view.addSubview(lineView)
            }
        }
    }
}

class DotView: UIView {
    enum DotType {
        case start
        case goal
        case normal
    }
    
    var otherDots: [DotView] = []
    var score: CGFloat = 0
    var type: DotType = .normal
    var routeDots: [DotView] = []
}

class LineView: UIView {
    let start: CGPoint
    let end: CGPoint
    let color: UIColor
    let lineWidth: CGFloat
    
    init(start: CGPoint, end: CGPoint, color: UIColor = UIColor.darkGray, lineWidth: CGFloat = 4) {
        self.start = start
        self.end   = end
        self.color = color
        self.lineWidth = lineWidth
        
        super.init(frame: CGRect(
            x: ([start.x, end.x].min() ?? 0) + 10,
            y: ([start.y, end.y].min() ?? 0) + 10,
            width: abs(start.x - end.x),
            height: abs(start.y - end.y)))
        
        backgroundColor = UIColor.clear
    }
    
    required init?(coder aDecoder: NSCoder) {
        fatalError("init(coder:) has not been implemented")
    }
    
    override func draw(_ rect: CGRect) {
        let path = UIBezierPath()
        path.lineWidth = lineWidth
        color.set()
        path.move(to: CGPoint(x: start.x - frame.origin.x + 10, y: start.y - frame.origin.y + 10))
        path.addLine(to: CGPoint(x: end.x - frame.origin.x + 10, y: end.y - frame.origin.y + 10))
        path.stroke()
    }
}

実際の計算は下の部分です。
スタートから順番に点を辿り、その順路が最短なら更に探索、最短でなければそのルートは探索終了しています。

if let start = dots.first {
    var targetDots = [start]
    while targetDots.count != 0 {
        let targetDot = targetDots.remove(at: 0)
        targetDot.otherDots.forEach {
            let dx = targetDot.frame.origin.x - $0.frame.origin.x
            let dy = targetDot.frame.origin.y - $0.frame.origin.y
            if $0.score == 0 || targetDot.score + sqrt(dx*dx + dy*dy) < $0.score {
                $0.score = targetDot.score + sqrt(dx*dx + dy*dy)
                targetDots.append($0)
                $0.routeDots = targetDot.routeDots + [targetDot]
            }
        }
    }
}

これを実行すると、以下のように最短経路を表示できた事が分かります。

f:id:llcc:20170520191211p:plain