ダイクストラ法という最短経路を求めるアルゴリズムを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)
}
}
}
次に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)
}
}
続けて線同士を繋げて経路を作ろうと思います。
各点に他経路への参照を持たせるためにDotViewというクラスを作って各点をUIViewからDotViewにします。
下だと場合によっては循環参照が起こったり場合によってゴールまで着けない事もあるのですが、今回は「ダイクストラ法」の勉強という事で無視します。
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)))))
}
}
}
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()
}
}
これで経路を作る事ができました。
ここからダイクストラ法を実装していきます。
まずは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]
}
}
}
}
これを実行すると、以下のように最短経路を表示できた事が分かります。
