파이썬 코딩테스트 스터디 8주차 #4 - 그래프 최단 경로 구하기

 

최단 경로는 그래프의 종류에 따라 그 진의가 다르게 해석

 

가중치가 없는 그래프 : 간선 개수가 가장 적은 경로

가중치가 있는 그래프 : 간선의 가충치의 총합이 최소

 

코딩 테스트 합격자 되기 : 파이썬 편 391p

노드 1에서 5까지 최단 경로 구할 때,

 

간선 개수 기준 : 1개가 최소

가중치 기준 : 1 → 2 → 5  (24)

 

 

최단 경로 대표 알고리즘 : 다익스트라 , 벨만-포드

 

다익스트라 알고리즘

 

1. 시작 노드 설정하고 시작 노드로부터 특정 노드까지의 최소 비용 저장할 공간, 직전 노드 저장할 공간 마련
   1. 최소 비용을 저장할 공간은 모두 매우 큰 값으로 초기화. 여기선 무한대(INF)로 표시, 직전 노드 저장도 INF
   2. 시작 노드의 최소비용:0, 직전 노드는 자기 자기 자신
2. 아직 방문하지 않은 노드 중 현재까지 구한 최소 비용이 가장 적은 노드 선택
   1. 해당 노드를 거쳐서 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용 비교. 작은 값을 각 조드의 최소 비용으로 갱신
   2. 이때 직전 노드도 같이 갱신
3. 노드 개수에서 1을 뺀만큼 반복

 

코딩 테스트 합격자 되기 : 파이썬 편 392p

코딩 테스트 합격자 되기 : 파이썬 편 393p

코딩 테스트 합격자 되기 : 파이썬 편 394p

코딩 테스트 합격자 되기 : 파이썬 편 395p

 

 

♬ 자료 출처 - 책

코딩 테스트 합격자 되기 - 파이썬 편

 

 

 

이 포스팅의 모든 내용은 해당 책의 내용을 바탕으로 하고 있습니다. 

감사합니다.