그래프의 한 노드에서 다른 노드까지의 경로 중 간선의 가중치의 합이 최소가 되는 경로를 찾는 알고리즘
그래프의 모든 간선의 가중치가 같거나, 가중치가 없을 경우
📍 구현 코드 예시
while (!q.empty()) { int node = q.front(); q.pop(); // front 노드 꺼내기 visited[node] = 1; // 방문 for (int i = 0; i < EDGE[node].size(); i++) { int neigh = EDGE[node][i]; // 인접 노드 if (visited[neigh] == -1) { q.push(neigh); dis[neigh] = dis[node] + 1; visited[neigh] = 1; /* 방문하지 않은 노드일 경우 Queue에 push 후 방문 표시, distance(거친 노드 수) update */ } } }
음의 가중치가 없는 그래프에서 Single Source, Single Destination, Single Pair 경로 탐색 가능
가중치 = min(update된 최단 경로에서의 가중치, 원래 가중치)
📍 구현 코드 예시
Dijkstra(const int n, const int v) { // n은 노드의 수, v는 시작점 for(int i=0; i<n; i++) { // initialize s[i] = false; // 방문 여부 dist[i] = length[v][i]; // 시작 점에서의 거리 } s[v] = true; // 시작점 방문 dist[v] = 0; // 시작점의 거리는 0 for(int i=0; i<n-2; i++) { // 시작점에서 n-1개의 path를 거쳐 목적지로 도달 int u = Choose(n); // 최단 경로를 가지는 노드 선택 s[u] = true; // 방문 for(int w=0; w<n; w++) if(s[w] == false) dist[w] = min(dist[u] + length[u][w], dist[w]); // update된 최단 경로를 가지고 다른 노드까지의 최단 경로 update }
음의 가중치를 포함하는 그래프에서 Single Source, Single Destination, Single Pair 경로 탐색 가능
D(v, k) = min{ D(v, k-1), min(D(d, k-1) + length(d, v)) }
📍 구현 코드 예시
BellmanFord(const int n, const int s) { // n은 노드의 수, s는 시작점 for(int i=0; i<n; i++) dist[i] = length[s][i] // 시작점에서의 경로 초기화 for(int k=2; k<n-1; k++) // n-1개의 경로 for(each v such that v != s and v has at least one incoming edge) // 시작점 외에 다른 점들까지 for(each <w, v> in the graph) dist[v] = min(dist[v], dist[w] + length[w][v]) // 최단경로 update }