[그래프] 위상 정렬, 최단 경로

위상 정렬

• 모든 간선에 대해 성질을 만족하는 순서로 작업을 정렬하는 것
• 위상 정렬은 싸이클이 없는 방향 그래프 G=(V,E) 에서 V의 모든 정덤을 정렬하되,
  '간선 (i->j)가 존재하면 정렬 결과에서 정점 i는 정점 j 보다 앞에 위치한다.' 라는 성질을 만족해야함
• 위상 정렬은 스케줄링이나, 가중치를 갖고 싸이클이 없는 방향 그래프의 최단 경로 찾기에도 쓰임
• 컴파일러에서 작업을 순차적으로 처리하기 위해서 사용되기도 함

 

 

최단 경로

• 모든 가능한 경로 중 최단 경로를 찾는 알고리즘
  • 다익스트라 알고리즘
    • 모든 간선 가중치가 양의 가중치인 싸이클
  • 벨만-포드 알고리즘
    • 음의 가중치를 허용하지만, 가중치 합이 양인 싸이클
• 다익스트라 알고리즘과 벨만-포드 알고리즘은 하나의 시작 정점으로부터 다른 모든 정점에 이르는 최단 경로를 구함

 

기초책이어서 그런지 관련 내용이 부족하게 느껴짐
이후에 다른 강의나 책에서 내용을 추가해야겠다

 

다익스트라 알고리즘(음의 가중치 허용X)

• 임의의 정점을 집합 S에 더할 때, r에서 그 정점까지의 최단 거리는 계산이 끝났다는 확신을 가지고 더함

 

벨만-포드 알고리즘(음의 가중치 허용 O)

• 동적 프로그래밍의 대표적인 예
• 최단 경로를 구하기 위해 거쳐가면 좋을 장소(보상을 주기)를 지나가도록 유도하는 것
• 입력 그래프 G=(V,E)에서 각 간선의 가중치가 음의 값을 허용하는 임의의 실수인 경우의 최단 경로 알고리즘
• 음의 싸이클을 절대 허용하지 않음

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」