목록최단경로 (1)
이숭간 공부기록
동빈나 2021 이코테 _ 7. 최단경로 알고리즘 ( 다익스트라)
최단경로 알고리즘이란, 가장 짧은 경로를 찾는 알고리즘 다양한 문제상황 한지점에서 다른 한지점 한 지점에서 다른 모든지점 모든 지점에서 다른 모든지점 각 지점은 그래프에서 노드로 표현하고 지점간 연결된 도로는 간선으로 표현함 ex ) 마을과 마을을 있는 도로, 도시를 있는 통로 등등 1. 다익스트라 알고리즘 특정한 노드(출발노드)에서 다른모든 노드로 가는 최단경로를 계산 (음의간선이 없을때) 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. (일종의 그리디 알고리즘) 동작과정 출발노드를 설정 최단거리 테이블을 초기화 (자기자신을 제외한 모든노드까지의 거리를 무한대로 설정, 자기자신은 0) 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택 ( 이 과정을 통해 특정 노드까지의 최단..
알고리즘/알고리즘 기초공부
2021. 3. 20. 19:04