0

More than 1 year has passed since last update.

# Swift で Dijkstra Algorithm（ダイクストラ法）使ってSSSP：Single Source Shortest Path（単一始点最短経路問題）

Last updated at Posted at 2021-09-02

Swift で Dijkstra Algorithm を書いたので備忘用にメモ

## NOTE

• 実装方法
• Dijkstra algo の実装方法としては大きく２通り（Naitve array / Primary Queue）あり、それぞれの実装方法によって Time Complexity が変わってくる
• 実装：DP

## Naive Array Way

• implementation: naive array
• start from 1-index
• Time Complexity: O(V^2) (V: number of vertexes)
``````struct Edge {
let to: Int
let weight:Int
}

// List does not use 0-index but starts from 1-indexrunning.
// n: number of nodes
// k: start node
func dijkstra(_ adjList: [[Edge]], _ n: Int, _ k: Int) -> ([Int], [Bool]){
var visited = [Bool](repeating: false, count: n+1)
var dist = [Int](repeating: Int.max, count: n+1)
visited[0] = true // no need 0-index
dist[0] = -1      // no need 0-index

// init
dist[k] = 0

// loop for all nodes
for _ in 1...n { // O(V)
// find vertex:
//   which is not visited yet.
//   whose dist is smallest
let minVertex: Int = { // O(V)
var minDist = Int.max // placeholder
var minVertex = -1    // placeholder
for vertex in 1...n { // nodes are at 1 to n
if visited[vertex] { continue }
if minDist > dist[vertex] {
minDist = dist[vertex]
minVertex = vertex
}
}
return minVertex
}()

// quick return
if minVertex == -1 { break }

// run the relaxation
let from = minVertex
let to = edge.to
let w = edge.weight
if dist[to] > dist[from] + w {
dist[to] = dist[from] + w
}
}

// visit
visited[minVertex] = true
}
return (dist, visited)
}
``````

## PQ Way

• implementation: Primary Queue
• start from 1-index
• Comparison to naive array:
• Improving find minVertex process with Heap. Time Complexity is changed O(V) to O(logV).
• Deteriorating to update store as PQ from O(1) to O(log V)

### Way1

けんちょん本の方法

``````// Before running, need a ready for IndexPriorityQueue, CompVertex.

func dijkstra(_ adjList: [[Edge]], _ n: Int, _ k: Int) -> ([Int], [Bool]){
var visited = [Bool](repeating: false, count: n+1)
var dist = [Int](repeating: Int.max, count: n+1)
visited[0] = true // no need 0-index
dist[0] = -1      // no need 0-index

// init
dist[k] = 0
visited[k] = true
var pq = PQ<CompVertex>(<) // min-heap
pq.enqueue(CompVertex(v: k, d: dist[k]))

// loop for all nodes
while let vertex = pq.dequeue() {
let v = vertex.v; let d = vertex.d;
if d > dist[v] { continue } // ignore because thsi is old info.
for edge in adjList[v] { // next edges
if dist[edge.to] > edge.weight + dist[v] {
dist[edge.to] = edge.weight + dist[v]
pq.enqueue(CompVertex(v: edge.to, d: dist[edge.to]))
}
}
visited[v] = true
}

return (dist, visited)
}

``````

### Way2

``````func dijkstra(_ adjList: [[Edge]], _ n: Int, _ k: Int) -> ([Int], [Bool]){
var visited = [Bool](repeating: false, count: n+1)
var dist = [Int](repeating: Int.max, count: n+1)
visited[0] = true // no need 0-index
dist[0] = -1      // no need 0-index

// init
dist[k] = 0
visited[k] = true
var pq = PQ<CompEdge>(<)
pq.enqueue(CompEdge(to: edge.to, d: edge.weight))
}

// loop for all nodes
while let edge = pq.dequeue() {
if dist[edge.to] > edge.d {
dist[edge.to] = edge.d
pq.enqueue(CompEdge(to: nextEdge.to, d: dist[edge.to] + nextEdge.weight))
}
visited[edge.to] = true
}
}

return (dist, visited)
}
``````

## MEMO

### Relaxation

``````if dist[to] > dist[from] + weight {
dist[to] = dist[from] + weight
}

// or

dist[to] = min(dist[to], dist[from] + weight)
``````

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
0