[algorithm] 다익스트라 알고리즘 (Dijkstra, 그래프)

다익스트라 알고리즘(Dijkstra algorithm)은 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘이다

출처: 나무위키

기회가 되면 코드 첨부예정

---

<다익스트라 알고리즘의 동작>

0. parameter

 - graph

 - src (출발 vertex)

1. init

 - 모든 vertex의 distance와 prev_vtx 초기화 (distance=INFINITE, prev_vtx=None)

 - src vertex의 distance=0

 - PQ <- 모든 vertex (priority=distance)

2. PQ 순회

 - src vertex부터 순회

 - 순회순서: 가까운 vertex 순서대로

---

<구현과정>

1. 가장 간단한 test-case

v1 -> v2 -> v3

   (3)   (5)

2. 다익스트라 함수 구현

 - high-level module부터 구현한다

def dijkstra(g, src):

...

3. 그래프 구현

 - detail implementation은 가장 마지막에 구현한다

class Graph:

...

---

<code example>

아래는 dist가 dict type인 version의 코드이다

# CONSTANT
INFINITY = 'INF'
dist = None
 
#################### high-level module ####################
 
def dijkstra(g, src):
    global dist
    
    ### init ###
    dist = {} # distance dict
    #prev = {} # prev_vtx dict
    pq = [] # distance priority queue
 
    for vtx in g.vtx_list:
        dist[vtx] = INFINITY
        #prev[vtx] = None
        pq.append(vtx)
    dist[g.vtx_list[src-1]] = 0
 
    ### round pq ###
    while len(pq) != 0:
        vtx1 = remove_min_vtx(pq)
        if dist[vtx1] == INFINITY:
            continue
        
        for edge in vtx1.adj_list: # 인접 정점들의 dist update
            vtx2 = edge.nxt
            new_dist = dist[vtx1] + edge.w # src->vtx1 + u->vtx2
            if is_smaller(new_dist, dist[vtx2]):
                dist[vtx2] = new_dist
                #prev[vtx2] = vtx1
    
    return dist
 
#################### detail implementation ####################
 
def remove_min_vtx(pq):
    min_vtx = pq[0]
    for vtx in pq:
        if is_smaller(dist[vtx], dist[min_vtx]):
            min_vtx = vtx
    
    pq.remove(min_vtx)
    return min_vtx
 
def is_smaller(a, b):
    if a == INFINITY:
        return False
    elif b == INFINITY:
        return True
    else:
        return a < b
 
class DirGraph: # directed, weighted, adj_list graph
    def __init__(self, vtx_cnt):
        self.vtx_list = []
        
        for i in range(vtx_cnt):
            i=i+1
            #print('add_vtx(%d)' % i)
            self.add_vtx(i)
    
    def add_vtx(self, idx):
        self.vtx_list.append(Vertex(idx))
 
    def add_edge(self, u, v, w):
        edge = Edge(self.vtx_list[u-1], self.vtx_list[v-1], w)
        self.vtx_list[u-1].adj_list.append(edge) # adj_list == fwd_list
 
class Vertex:
    def __init__(self, idx):
        self.idx = idx
        self.adj_list = []
        
    def __str__(self):
        result = 'vtx_%d { ' % self.idx
        for edge in self.adj_list:
            result += '%s ' % edge
        return result+'}'
 
class Edge:
    def __init__(self, prev, nxt, weight):
        self.prev = prev
        self.nxt = nxt
        self.w = weight
        
    def __str__(self):
        return '(%d,%d,%d)' % (self.prev.idx, self.nxt.idx, self.w)
 
def main():
    vtx_cnt, edge_cnt = (int(i) for i in input('vtx_cnt, edge_cnt: ').split())
    src = int(input('src: '))
    g = DirGraph(vtx_cnt)
    
    for i in range(edge_cnt):
        u, v, w = (int(i) for i in input('u,v,w: ').split())
        g.add_edge(u, v, w)
        
    for v in g.vtx_list:
        print(v)
    
    dist = dijkstra(g, src)
    for key in dist:
        print(key, dist[key])        
 
def test_main():
    vtx_cnt, edge_cnt = 5,6
    src = 1
    g = DirGraph(vtx_cnt)
 
    g.add_edge(5,1,1)
    g.add_edge(1,2,2)
    g.add_edge(1,3,3)
    g.add_edge(2,3,4)
    g.add_edge(2,4,5)
    g.add_edge(3,4,6)
 
    for v in g.vtx_list:
        print(v)
    
    dist = dijkstra(g, src)
    for key in dist:
        print(key, dist[key])
 
#main()
test_main()

아래는 dist가 list type인 version의 코드이다

또한 백준 알고리즘 (ACM-ICPC) 1753번 문제의 정답코드이다

주석(코드설명)은 아래 포스팅에서

http://ssaemo.tistory.com/109

# CONSTANT
INFINITY = 'INF'
 
#################### high-level module ####################
 
def dijkstra(g, src):
    dist = [None] # distance list
    pq = [] # vertex pq (distance priority)
 
    for vtx in g.vtx_list[1:]:
        dist.append(INFINITY)
        pq.append(vtx)
    dist[src] = 0
 
    ### round pq ###
    while len(pq) != 0:
        vtx1 = remove_min_vtx(pq, dist)
        if dist[vtx1.idx] == INFINITY:
            break
        
        for edge in vtx1.adj_list: # 인접 정점들의 dist update
            vtx2 = edge.nxt
            new_dist = dist[vtx1.idx] + edge.w # src->vtx1 + u->vtx2
            if is_smaller(new_dist, dist[vtx2.idx]):
                dist[vtx2.idx] = new_dist
    
    return dist
 
#################### detail implementation ####################
 
# function of distance PQ
def remove_min_vtx(pq, dist):
    min_vtx = pq[0]
    for vtx in pq:
        if is_smaller(dist[vtx.idx], dist[min_vtx.idx]):
            min_vtx = vtx
    
    pq.remove(min_vtx)
    return min_vtx
 
# dist list function
def is_smaller(a, b):
    if a == INFINITY:
        return False
    elif b == INFINITY:
        return True
    else:
        return a < b
 
class DirGraph: # directed, weighted, adj_list graph
    def __init__(self, vtx_cnt):
        self.vtx_list = [None]
        
        for i in range(vtx_cnt):
            i=i+1
            self.add_vtx(i)
    
    def add_vtx(self, idx):
        self.vtx_list.append(Vertex(idx))
 
    def add_edge(self, u, v, w):
        edge = Edge(self.vtx_list[u], self.vtx_list[v], w)
        self.vtx_list[u].adj_list.append(edge) # adj_list == fwd_list
 
class Vertex:
    def __init__(self, idx):
        self.idx = idx
        self.adj_list = []
        
    def __str__(self):
        result = 'vtx_%d { ' % self.idx
        for edge in self.adj_list:
            result += '%s ' % edge
        return result+'}'
 
class Edge:
    def __init__(self, prev, nxt, weight):
        self.prev = prev
        self.nxt = nxt
        self.w = weight
        
    def __str__(self):
        return '(%d,%d,%d)' % (self.prev.idx, self.nxt.idx, self.w)
 
def main():
    vtx_cnt, edge_cnt = (int(i) for i in input().split())
    src = int(input())
    g = DirGraph(vtx_cnt)
    
    for i in range(edge_cnt):
        u, v, w = (int(i) for i in input().split())
        g.add_edge(u, v, w)
    
    dist = dijkstra(g, src)
    for i in dist:
        print(i)
 
def test_main():
    vtx_cnt, edge_cnt = 5,6
    src = 1
    g = DirGraph(vtx_cnt)
 
    g.add_edge(5,1,1)
    g.add_edge(1,2,2)
    g.add_edge(1,3,3)
    g.add_edge(2,3,4)
    g.add_edge(2,4,5)
    g.add_edge(3,4,6)
 
    print('<vtx_list>')
    for v in g.vtx_list[1:]:
        print(v)
    
    dist = dijkstra(g, src)
    print('\n<result>')
    for i in dist:
        print(i)
 
main()