1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 | # 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() | cs |
주석 추가예정
'Algorithm' 카테고리의 다른 글
[algorithm] Sorting(정렬)의 종류 - PQ, Merge, Quick (0) | 2017.12.16 |
---|---|
[algorithm] 우선순위 큐(PQ) 구현의 종류 (0) | 2017.12.16 |
[algorithm] 그래프 기초 (0) | 2017.12.14 |
[algorithm] 백준 알고리즘 1005번 문제 정답코드 (0) | 2017.12.14 |
[algorithm] 다익스트라 알고리즘 (Dijkstra, 그래프) (0) | 2017.12.14 |
WRITTEN BY
- hojongs
블로그 옮겼습니다 https://hojongs.github.io/