[자료구조와 알고리즘] 최단 경로(플로이드 와샬, 다익스트라)

geesuee·2021년 9월 22일
0

??? : 세상은 최단 경로만 기억해!(?) 최단 경로 구하기 기릿!


📖 최단 경로를 구하는 알고리즘

✅ 출발지부터 도착지까지 최단 거리/최소 비용을 지불하는 경로 구하기
✅ 최단 경로를 구하는 알고리즘 중 대표적 두 가지 : 플로이드 와샬 알고리즘 , 다익스트라 알고리즘


1. 플로이드 와샬 알고리즘

존재하는 모든 노드를 최소 비용으로 방문하는 최단 경로 탐색
모든 정점에서 모든 정점으로
✅ 동적 계획법(dynamic programming)에 의거

ㄴ 거쳐가는 정점을 기준으로 최단 거리 구함

ㄴ 전체 노드 연결 최단 거리 연산


구현 방법

  • 비용 배열과 방문 배열 선언
  • 비용 배열에는 maxsize 값을, 방문 배열에는 false 값을 넣어 초기화
  • 시작 노드를 정하고, 시작 노드 인덱스의 비용 배열 값은 0, 방문 배열 값은 true로 갱신
  • 해당 노드에서 이동 가능한 노드 인덱스의 비용 배열 값 (각각의 이동 비용으로)갱신
  • 그 중에서 가장 작은 값을 갖는 노드로 이동, 해당 노드 인덱스의 방문 배열 값 true로 갱신
  • 이동한 노드에서 이동 가능한 노드 인덱스의 비용 배열 값 갱신,
    maxsize가 아닌 값이 있다면 바로 전 노드에서 해당 노드로 이동하는 비용만 고려하여 더 작은 값으로 갱신
  • 이동 가능한 노드 중에서 이동 비용이 가장 작은 노드로 이동, 방문 배열 값 갱신
  • 방문 배열 값이 모두 true가 될 때까지(=모든 노드를 방문할 때까지) 위 과정 반복
  • 비용 배열에 있는 모든 값을 더해 최단 거리 방문시 필요한 비용 연산



2. 다익스트라 알고리즘

특정 노드에서 다른 노드까지의 최단 경로 탐색
특정 정점에서 각각의 다른 정점으로
✅ 동적 계획법(dynamic programming) 활용, 대표적인 최단 경로 탐색 알고리즘
= 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문
❌ 음의 간선은 포함할 수 없음

ㄴ 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 사용, 갱신

ㄴ 출발점 ~ 다른 노드 최단 거리 연산


구현 방법

  • 비용 배열과 방문 배열 선언
  • 비용 배열에는 maxsize 값을, 방문 배열에는 false 값을 넣어 초기화
  • 출발점 노드를 정하고, 시작 노드 인덱스의 비용 배열 값은 0, 방문 배열 값은 true로 갱신
  • 해당 노드에서 이동 가능한 노드 인덱스의 비용 배열 값 (각각의 이동 비용으로)갱신
  • 그 중에서 가장 작은 값을 갖는 노드로 이동, 해당 노드 인덱스의 방문 배열 값 true로 갱신
  • 이동한 노드에서 이동 가능한 노드 인덱스의 비용 배열 값 갱신,
    maxsize가 아닌 값이 있다면 누적 비용을 계산하여 더 작은 값으로 갱신
  • 이동 가능한 노드 중에서 이동 비용이 가장 작은 노드로 이동, 방문 배열 값 갱신
  • 방문 배열 값이 모두 true가 될 때까지(=모든 노드를 방문할 때까지) 위 과정 반복
  • 비용 배열의 각 값이 출발점 노드로부터 해당 인덱스 노드까지 이동하는 최소 비용
profile
기록하는 오늘의 노력🌻

0개의 댓글