떠도는..개발자 취준생

정리 1. 에지의 가중치가 양수인 연결된 그래프에서 사용 2. 한 정점으로부터 연결된 모든 정점에 대한 최단 경로를 구하는 알고리즘 3. 욕심쟁이 알고리즘(Greedy Algorithm) V : 정점들의 집합 D[v] : 시작정점 s로부터 정점 v까지의 최단거리 S : 시작정점 s로부터 최단 경로를 찾은 정점들의 집합 다익스트라 알고리즘은 매 선택에서 최적의 답을 선택하여 적합한 결과를 도출하는 욕심쟁이 알고리즘을 기반으로 두고있다. 여기서 매 선택은 연결된 노드들 중 탐색을 할 노드를 선택하는 과정이며, 최적의 답은 연결된 노드들 중에서 거리가 최소인 노드이다. 다익스트라 알고리즘은 시작 노드를 기준으로 모든 노드의 최단 거리를 구하는 알고리즘으로 시작 노드의 거리를 0, 나머지의 거리는 무한으로 설정..

그래프의 정의 그래프는 정점(노드)와 간선(엣지)의 집합으로 이루어진 자료구조를 의미한다. 간선은 한 쪽 방향으로만 이동 가능한 단방향 그래프와 양 방향으로 모두 이동 가능한 무방향 그래프로 나뉘어진다. 그래프 용어 부그래프 그래프 G=(V,E)의 부그래프 G'=(V',E')은 V'는 V의 부분집합, G'는 G의 부분집합인 그래프를 의미한다. 완전그래프 완전그래프는 모든 정점 사이에 엣지가 있는 그래프이다. 연결그래프 그래프의 정점들 중 임의의 두 정점 u1,u2에 대하여 u1부터 u2까지의 경로가 존재하는 그래프이다. 만약 그래프가 단방향그래프이고 u1부터 u2까지의 경로가 존재한다면 해당 연결그래프를 강연결그래프라고 한다. 그래프 표현 그래프의 정접 집합 V={v0, v1, v2 ... v(n-1)}..