![]()
정의BFS랑 다익스트라 차이점 ⇒ 가중치 여부(음수 가중치는 고려 X → 음수 가중치는 벨만포드)가중치가 없으면 BFS, 가중치가 있으면 다익스트라 사용BFS로는 최소 비용을 구할 수 없다.물론, 노드 수와 가중치가 많이 작다면 더미 노드를 만들어서 구현할 수는 있다.다익스트라로 접근하기거리 배열 초기 상태시작 노드를 1번으로 했기 때문에 dist[1] = 0, 나머지는 매우 큰 값으로 초기화하고 시작12345670∞∞∞∞∞∞거리가 제일 작은 1번 노드부터 시작1번 방문 처리 & 주변 노드 거리 갱신123456701500100∞∞∞방문 체크가 안 된 노드 중 거리가 제일 작은 2번 노드 탐색2번 방문 처리 & 주변 노드 거리 갱신거리 갱신할 때 1번 노드 부터 해당 노드까지 거리 중 최솟값으로 갱신한다...
![]()
플로이드 워셜 알고리즘 정의음수 사이클이 없는 그래프 내의 각 모든 정점에서 각 모든 정점까지의 최단거리를 구할 수 있는 알고리즘음수 사이클만 아니면, 음수 가중치를 갖는 간선이 존재해도 상관 x사용법인접 행렬 그래프 생성 ⇒ 초기화0개의 간선을 거쳐 모든 노드로 가는 방법자기 자신으로 갈 때 → 0그 외 다른 노드로 갈 수 있는 방법이 없으므로, 무한대 INF 값으로 초기화1개의 간선을 거쳐 모든 노드로 가는 경우 = 주어진 그래프에서 직접 연결된 경우를 생각해당 간선의 가중치로 초기화이때, 노드간 간선이 여러개 존재한다면 가장 작은 가중치 선택위 방식으로 0개 ~ N개의 간선을 거친 경우의 최소 거리 비용을 비교하여, 인접행렬을 갱신해나간다.3개의 중첩 루프를 사용해 각 정점 쌍에 대한 최단 경로 갱..
