Written by
Lee Jongseo
on
on
Alogrithm[7]:⭐⭐ - Dijkstra’s algorithm(Shortest Path)
Dijkstra’s algorithm
an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
- source node
s에서 다른 nodes로 가는 shortest path를 구하데 사용하는 알고리즘 - Dijkstra는 알고리즘을 만든 독일 출생의 컴퓨터 과학자인 Edsger W. Dijkstra의 이름에서 따온 것.
Pseudocode 분석
Pseudocode의 출처 -> https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Using_a_priority_queue
1 function Dijkstra(Graph, source):
2 dist[source] ← 0 // Initialization
3
4 create vertex priority queue Q
5
6 for each vertex v in Graph:
7 if v ≠ source
8 dist[v] ← INFINITY // Unknown distance from source to v
9 prev[v] ← UNDEFINED // Predecessor of v
10
11 Q.add_with_priority(v, dist[v])
12
13
14 while Q is not empty: // The main loop
15 u ← Q.extract_min() // Remove and return best vertex
16 for each neighbor v of u: // only v that are still in Q
17 alt ← dist[u] + length(u, v)
18 if alt < dist[v]
19 dist[v] ← alt
20 prev[v] ← u
21 Q.decrease_priority(v, alt)
22
23 return dist, prev