'2024/11/25 글 목록

이전 글에서 그래프에서 cycle이 만들어지지 않으며 모든 정점을 연결하는 MST를 kruskal 알고리즘으로 만들어보았다. 이번에는 그래프에서 시작 정점에서 특정 정점까지 최단거리로 연결하는 길을 찾는 방법을 알아볼 것이며 dijkstra 알고리즘을 이용할 것이다.최단경로 찾기 알고리즘Dijkstra의 최단 경로 알고리즘의 단계는 다음과 같다.집합에서 가장 짧은 경로의 정점 u를 집합에 추가집합에 없는 다른 정점까지의 거리 업데이트u를 거쳐 가는 경로가 더 짧으면 해당 값으로 업데이트이게 가능한 이유는 집합에서 가장 가까운 정점 u를 선택하면, u로 가는 더 가까운 길은 없기 때문이다.C언어 구현 방법그래프 구조체에는 vertex의 수 n과, 정점간 간선의 weight(거리)를 의미하는 2차원 배열 w..