그래프: G = (V,E)
- V vertices 정점 E edge 간선
- |V| 정점 수 |E| 정점 수
그래프의 종류와 선언
[그래프] 인접 행렬과 인접 리스트
그래프 관련 문제를 풀 때는, 문제 상황을 그래프로 모델링한 후에 푸는 것이 보편적입니다. 이 때, 모델링한 그래프의 연결관계를 나타내는 두 가지 방식이 있습니다. 1. 인접 행렬 2. 인접 리스
sarah950716.tistory.com
그래프 내에서 노드의 최단 경로를 구하는 방법
1. 하나의 정점에서 다른 하나의 정점까지 최단 경로 구하기 single source and single destination shortest path problem
2. 하나의 정점에서 다른 모든 정점까지의 최단 경로 구하기 single source shortest path problem
: 다익스트라 알고리즘
[알고리즘] Dijkstra 다익스트라 알고리즘
- 한 정점에서 여러 개의 다른 정점까지의 최단 거리를 구하는 알고리즘 (single source shortest path) - 간선에 양의 가중치가 존재한다. (음의 가중치까지 있는 건 벨만포드 알고리즘) - 구현시 배열 혹
eazymean.tistory.com
3. 하나의 목적지로 가는 모든 최단 경로 구하기 single destination shortest path problem
4. 최단 경로 구하기 all pairs shortest path problem
: 플로이드 워셜 알고리즘
https://eazymean.tistory.com/9
[알고리즘] Floyd-Warshall 알고리즘
모든 최단 경로를 구하는 방법 all pairs shortest path problem 그래프 종류: weighted, directed graph G = (V,E) 이때 weight func w: E->R (R은 실제 weight값, edge에 weight를 매핑한다.) 경로 p의 weight w..
eazymean.tistory.com
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘] Tree Traversal - Depth First Traversal (0) | 2020.10.04 |
|---|---|
| [알고리즘] Prefix Sum 구간 합/누적 합 알고리즘 (0) | 2020.10.01 |
| [알고리즘] Sliding Window 슬라이딩 윈도우 (0) | 2020.09.30 |
| [알고리즘] Floyd-Warshall 알고리즘 (0) | 2020.03.13 |
| [알고리즘] Union-Find (0) | 2020.03.13 |
댓글