간선 완화2 [알고리즘] ep7+) 다익스트라와 벨만-포드 알고리즘 구현 주의: 그래프 알고리즘 구현 시, 그래프의 인접 정보(즉, 부착 간선리스트 또는 인접행렬) 없이도 수행 가능한 문제라고 판단되면 간선리스트 구조로 그래프를 간편하게 구현할 것을 우선적으로 고려하라. 그렇지 않고, 인접 정보가 있어야 수행한다고 판단되면 인접리스트 구조 또는 인접행렬 구조 중에 해당 문제 해결에 효율성 면에서 유리하다고 판단되는 것을 선택하여 구현하라. 문제1) 무방향 양의 가중그래프 -> 다익스트라 알고리즘무방향 양의 가중그래프(undirected weighted graph) G와 출발정점이 주어지면, 출발정점에서 다른 모든 정점으로 가는 최단거리를 구하는 프로그램을 작성하라. 입력 그래프의 성질:◦ n(1 ≤ n ≤ 100)개의 정점과 m(1 ≤ m ≤ 1,000)개의 간선으로 구성.. 2024. 7. 27. [알고리즘] ep7) 최단경로 ㅁ최단경로 문제(shortest path problem): 가중그래프 두 개의 정점 u와 v가 주어졌을 때, u와 v 사이의 무게의 합이 최소인 경로를 구하는 문제최단경로길이: 간선들의 무게 합 응용: 인터넷 패킷 라우팅, 항공편 예약, 자동차 네비게이션 [최단경로 속성 2가지]속성1)최단경로의 부분경로(subpath) 역시 최단경로이다 속성2)출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다 - 단일점 최단경로(single-source shortest path) - 최단경로는 무방향뿐만 아니라 방향그래프에서도 정의가 가능하다- 그래프에 음의 무게를 가진 싸이클이 있거나, 무방향그래프에 음의 무게를 가진 간선이 있으면 부정한다- 최단경로트리(shortest path tree)는 루트.. 2024. 7. 26. 이전 1 다음
