문제해결 전략 - 30. 최단 경로 알고리즘

최단경로 문제

주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제

• 가중치가 있는 그래프에서의 최단 경로를 찾는 알고리즘을 다룬다.
• 최단 경로를 구성하는 정점들의 목록을 구해주는 것이 아니기 때문에 실제 경로를 계산하기 위해서는 별도의 정보를 저장해야 한다.
• 다양한 그래프의 종류와 특성에 따라 최적화된 많은 최단 경로 알고리즘이 존재한다

음수 간선의 중요성

• 음수 간선을 지나가면 전체 경로의 길이가 짧아진다.
• 음수 사이클이 있을 경우 경로의 길이는 음의 무한대로 발산 할 수 있다.
• 그래서 최단 경로를 찾을 수 없으며 음수 사이클이 존재한다는 것만 확인할 수 있다.

단일 시작점과 모든 쌍의 알고리즘

• 단일 시작점 알고리즘 : 너비 우선 탐색과 비슷하게, 하나의 시작점에서 다른 모든 정점까지 가는 최단 거리 계산
• 모든 쌍 알고리즘 : 모든 정점의 쌍에 대한 최단 거리를 계산

---

다익스트라의 최단 경로 알고리즘

• 단일 시작점 최단 경로 알고리즘
• 시작 정점 s에서 부터 다른 정점까지의 최단 거리를 계산

우선순위 큐를 사용하는 너비 우선 탐색

• 우선순위 큐에 정점의 번호와 함께 지금까지 찾아낸 해당 정점 까지의 최단 거리를 쌍으로 넣는다.
• 우선순위 큐는 정점까지의 최단 거리를 기준으로 정점을 배열해서 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는 과정을 간단하게 해준다.
• 각 정점까지의 최단 경로가 갱신될 수 있다.
  이 경우 원래 있던걸 그대로 두고 새로운 걸 추가한 뒤 나중에 원래있던게 꺼내지면 무시한다
  
  

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Dijkstra {
    public void computePath(Vertex sourceVertex) {
        sourceVertex.setMinDistance(0);
        PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(sourceVertex);

        while (!priorityQueue.isEmpty()) {
            Vertex vertex = priorityQueue.poll();

            for (Edge edge : vertex.getEdges()) {
                Vertex v = edge.getTargetVertex();
//                Vertex u = edge.getStartVertex();
                double weight = edge.getWeight();
                double minDistance = vertex.getMinDistance() + weight;

                if (minDistance < v.getMinDistance()) {
                    priorityQueue.remove(vertex);
                    v.setPreviosVertex(vertex);
                    v.setMinDistance(minDistance);
                    priorityQueue.add(v);
                }
            }
        }
    }

    public List<Vertex> getShortestPathTo(Vertex targetVerte) {
        List<Vertex> path = new ArrayList<>();

        for (Vertex vertex = targetVerte; vertex != null; vertex = vertex.getPreviosVertex()) {
            path.add(vertex);
        }

        Collections.reverse(path);
        return path;
    }
}

---

다익스트라 알고리즘 동작 과정

동작과정

 

다익스트라 알고리즘 시간 복잡도

• 정점마다 인접한 간선을 모두 검사하는 작업 : O(|E|)
• 우선순위 큐에 원소를 넣고 삭제하는 작업 : O(|E| lg |E|)
• O(|E| lg |V|)

---

벨만-포드의 최단 경로 알고리즘

• 다익스트라 알고리즘은 음수 간선이 있을 경우 정당성이 보장되지 않는다.
• 단일 시작점 최단 경로 알고리즘
• 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있다.
• 그래프에 음수 사이클이 있어서 최단 거리가 제대로 정의되지 않을 경우도 알려준다.
• 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여나가는 방식으로 동작한다.
• 수행 과정에서 각 정점까지의 최단 거리의 상한을 담는 배열 upper[]를 유지한다.

벨만-포드의 동작과정

• 알고리즘이 시작할 땐 그래프의 구조를 모른다.
• 시작점에서 시작점까지 거리는 0이고 나머지는 아주 큰 수로 초기화 한다.
• relax 과정을 반복적으로 실행하며 최단 거리에 가까워 진다.

음수 사이클의 판정

• 음수사이클의 존재 여부를 판정정하려면 |V|-1번 모든 간선에 대한 relax를 시도하는 대신 |V|번 relax를 시도하면 된다.
• 그래프에 음수 사이클이 없다면 |V|-1 번만의 반복으로 모든 최단 거리를 찾아내기 때문에 마지막 반복의 완화는 전부 실패한다.

벨만-포트 알고리즘의 구현

// A Java program for Bellman-Ford's single source shortest path 
// algorithm. 
import java.util.*; 
import java.lang.*; 
import java.io.*; 

// A class to represent a connected, directed and weighted graph 
class Graph { 
	// A class to represent a weighted edge in graph 
	class Edge { 
		int src, dest, weight; 
		Edge() 
		{ 
			src = dest = weight = 0; 
		} 
	}; 

	int V, E; 
	Edge edge[]; 

	// Creates a graph with V vertices and E edges 
	Graph(int v, int e) 
	{ 
		V = v; 
		E = e; 
		edge = new Edge[e]; 
		for (int i = 0; i < e; ++i) 
			edge[i] = new Edge(); 
	} 

	// The main function that finds shortest distances from src 
	// to all other vertices using Bellman-Ford algorithm. The 
	// function also detects negative weight cycle 
	void BellmanFord(Graph graph, int src) 
	{ 
		int V = graph.V, E = graph.E; 
		int dist[] = new int[V]; 

		// Step 1: Initialize distances from src to all other 
		// vertices as INFINITE 
		for (int i = 0; i < V; ++i) 
			dist[i] = Integer.MAX_VALUE; 
		dist[src] = 0; 

		// Step 2: Relax all edges |V| - 1 times. A simple 
		// shortest path from src to any other vertex can 
		// have at-most |V| - 1 edges 
		for (int i = 1; i < V; ++i) { 
			for (int j = 0; j < E; ++j) { 
				int u = graph.edge[j].src; 
				int v = graph.edge[j].dest; 
				int weight = graph.edge[j].weight; 
				if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) 
					dist[v] = dist[u] + weight; 
			} 
		} 

		// Step 3: check for negative-weight cycles. The above 
		// step guarantees shortest distances if graph doesn't 
		// contain negative weight cycle. If we get a shorter 
		// path, then there is a cycle. 
		for (int j = 0; j < E; ++j) { 
			int u = graph.edge[j].src; 
			int v = graph.edge[j].dest; 
			int weight = graph.edge[j].weight; 
			if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) { 
				System.out.println("Graph contains negative weight cycle"); 
				return; 
			} 
		} 
		printArr(dist, V); 
	} 

	// A utility function used to print the solution 
	void printArr(int dist[], int V) 
	{ 
		System.out.println("Vertex Distance from Source"); 
		for (int i = 0; i < V; ++i) 
			System.out.println(i + "\t\t" + dist[i]); 
	} 

	// Driver method to test above function 
	public static void main(String[] args) 
	{ 
		int V = 5; // Number of vertices in graph 
		int E = 8; // Number of edges in graph 

		Graph graph = new Graph(V, E); 

		// add edge 0-1 (or A-B in above figure) 
		graph.edge[0].src = 0; 
		graph.edge[0].dest = 1; 
		graph.edge[0].weight = -1; 

		// add edge 0-2 (or A-C in above figure) 
		graph.edge[1].src = 0; 
		graph.edge[1].dest = 2; 
		graph.edge[1].weight = 4; 

		// add edge 1-2 (or B-C in above figure) 
		graph.edge[2].src = 1; 
		graph.edge[2].dest = 2; 
		graph.edge[2].weight = 3; 

		// add edge 1-3 (or B-D in above figure) 
		graph.edge[3].src = 1; 
		graph.edge[3].dest = 3; 
		graph.edge[3].weight = 2; 

		// add edge 1-4 (or A-E in above figure) 
		graph.edge[4].src = 1; 
		graph.edge[4].dest = 4; 
		graph.edge[4].weight = 2; 

		// add edge 3-2 (or D-C in above figure) 
		graph.edge[5].src = 3; 
		graph.edge[5].dest = 2; 
		graph.edge[5].weight = 5; 

		// add edge 3-1 (or D-B in above figure) 
		graph.edge[6].src = 3; 
		graph.edge[6].dest = 1; 
		graph.edge[6].weight = 1; 

		// add edge 4-3 (or E-D in above figure) 
		graph.edge[7].src = 4; 
		graph.edge[7].dest = 3; 
		graph.edge[7].weight = -3; 

		graph.BellmanFord(graph, 0); 
	} 
} 
// Contributed by Aakash Hasija 

---

플로이드의 모든 쌍 최단 거리 알고리즘

모든 쌍 간의 최단 거리를 구하고 싶을 때 사용

 

 

 

Resource

dijkstra.gif Source View,Pictures preview,Source program download - interviews

Dijkstra Algorithm in Java

 

Back to Basics — Divine Algorithms Vol II: Bellman-Ford Algorithm

 

Bellman–Ford Algorithm | DP-23 - GeeksforGeeks