비전공 개발자의 일지

1. 벨만-포드 알고리즘단일 출발점 최단 경로를 구하는 알고리즘음의 가중치를 갖는 간선이 존재하는 경우에도 처리 가능단, 음의 사이클이 없는 경우에만 동작함G=(V, E)에서 |V|=n일 때, 단계적으로 최단 경로를 구해 나가는 방식간선을 최대 1개 사용하는 최단 경로간선을 최대 2개 사용하는 최단 경로…간선을 최대 (n-1)개 사용하는 최단 경로수행 과정초기화출발점 s의 거리 d[s] = 0나머지 모든 정점 v의 거리 d[v] = ∞for i ← 1 to |V| - 1모든 간선을 한 번씩 조사하면서 거리값 조정 여부 결정d[v] ← min{ 기존 거리 d[v], 간선 ⟨u, v⟩를 지나는 경우의 거리 d[u] + w }전 단계에서 거리값 d[ ]의 조정이 발생한 정점에 부수된 간선만 조사하는 방식으로 ..