[알고리즘][Graph] 최단 경로(Shortest Path) #1 최단 경로 문제, Bellman-Ford 알고리즘

학습목표
1. 최단 경로의 개념에 대해서 학습
2. 최단 경로 문제의 유형과 특징에 대해서 학습
3. Single-Source 최단 경로 문제에 대해서 학습
4. Bellman-Ford 알고리즘에 대해서 학습
5. Java언어 기반 Bellman-Ford 알고리즘 구현

 

1. 최단 경로란 무엇인가?

그래프에서 최단 경로란 방향, 무방향 그래프 상관없이 특정한 노드 u,v가 주어졌을때 u노드부터 시작하여 v노드까지 가는 경로중에서 가중치의 합이 최소인 경로를 최단 경로라고 합니다. 이를 기호로 표시하면 δ(u,v)로 표시하기도 합니다.

 

위 그림에서 노드 A에서 출발하여 노드 F까지 도착하는 여러 경로 중에서 최단 경로는 A->C->E->D->F인 것을 알수 있습니다.

 

2. 최단 경로 문제의 유형

• Single-Source
  • 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 탐색
  • 예 : 다익스트라(Dijkstra) 알고리즘
• Single-destination
  • 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 탐색
  • Single-Source 문제와 동일
  • 모든 에지의 방향을 반대로하면 Single-Source 문제로 변형이 가능함
• Single-Pair
  • 주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 탐색
  • 최악의 경우 시간복잡도에서 Single-Source 문제보다 나은 알고리즘이 없음
• All-Paris
  • 모든 노드 쌍에 대해서 최단 경로를 탐색
  • 예 : Floyed 알고리즘

 

최단 경로와 음수 가중치

최단 경로를 탐색할때 그래프 간선의 가중치가 음수를 가질수도 있습니다. 그래서 음수 사이클이 있다면 최단 경로가 정의되지 않을수도 있습니다. 따라서 많은 알고리즘들이 음수 가중치가 없다고 가정(예를 들어 다익스트라 알고리즘)하고 수행합니다.

3. 최단 경로의 기본 특성

1. 최단 경로의 어떤 부분 경로도 역시 최단 경로입니다.
   
   • 왜냐하면 노드 u에서 v까지의 최단 경로를 탐색하기 위해서는 최종 최단 경로의 부분적인 노드들까지도 부분적으로 최단 경로를 완성해야 하기 때문입니다.
2.  최단 경로는 사이클을 포함하지 않습니다. (음수 사이클이 없다는 가정하에서)
   • 최단 경로는 노드 u에서 v까지 가는 가중치가 최소인 경로이므로 같은 노드를 2번 방문할 필요가 없기 때문입니다.

 

4. Bellman-Ford 알고리즘

Bellman-Ford 알고리즘은 Single-source 문제의 유형으로써 그래프에서 최단 경로를 탐색하는 알고리즘입니다. 그래프와 시작 노드가 주어졌을때 시작 노드에서부터 그래프의 모든 노드까지의 최단 경로를 탐색합니다. 주어진 그래프는 음수 가중치 간선이 포함될 수 있습니다.

 

음수 가중치 간선이 없다는 것을 가정한 다익스트라 알고리즘과는 다르게 Bellman-Ford 알고리즘은 음수 가중치가 있어도 최단 경로가 존재하면 탐색할 수 있습니다. 단, 만약 음수 사이클이 존재한다면 최단 경로가 없기 때문에 결과를 내지 못합니다.

 

Bellman-Ford 알고리즘 수행과정

• 입력 : 그래프와 시작 노드(start)
• 출력 : 시작 노드부터 모든 노드까지의 최단 거리, 만약 음수 사이클이 존재하면 최단 거리를 출력하지 않음

1. dist 배열(노드의 개수(V)만큼)을 생성하고 시작 노드와 다른 노드들의 거리(distance)를 초기화합니다.
   • dist[start] = 0
   • dist[v] = Integer.MAX, v는 start를 제외한 다른 노드들
   • 예를 들어 dist[u]=5의 의미는 u까지의 최단 경로의 가중치 합이 5라는 의미입니다.
2. 최단 경로를 계산합니다. 아래의 과정을 |V|-1번 반복합니다.
   • 각각의 간선 (u,v)에 대하여 만약 dist[u] + (u,v)의 가중치 합계가 dist[v]보다 작다면 이는 해당 경로가 더 최단 경로이므로 dist[v]의 값을 dist[u] + (u,v)의 가중치로 갱신합니다.
3. 2번 과정을 수행한 다음 그래프에 음수 사이클이 존재하는지 검사합니다.
   1. 각각의 간선 (u,v)에 대하여 만약 dist[u]+(u,v)의 가중치 합계가 dist[v]보다 작다면 음수 사이클이 있는 것이므로 실행을 종료합니다.

아래의 그림은 Bellman-Ford 알고리즘 수행과정을 그림으로 표현한 것입니다.

 

 

5. Java언어 기반 Bellman-Ford 알고리즘 구현

	public void bellmanFord(int start)
	{
		int[] dist = new int[V];
		int[] predesor = new int[V];
		
		// step1 초기화
		for(int i=0;i<V;i++)
		{
			dist[i] = Integer.MAX_VALUE;
			predesor[i] = i;
		}
		dist[start] = 0;
		
		// step2 최단 경로 갱신
		for(int i=0;i<V;i++)
		{	
			for(int e=0;e<V;e++)
			{
				for(Edge edge : adj_weight.get(e))
				{
					int u = edge.src;
					int v = edge.dest;
					int w = edge.weight;
					
					if(dist[u]!=Integer.MAX_VALUE &&
							dist[u] + w < dist[v])
					{
						dist[v] = dist[u] + w;
						predesor[v] = u;
					}
				}
			}	
		}
		
		// step3	음수 사이클이 있는지 검사
		for(int i=0;i<V;i++)
		{
			for(Edge edge : adj_weight.get(i))
			{
				int u = edge.src; 
				int v = edge.dest;
				int w = edge.weight;
				
				if(dist[u]!=Integer.MAX_VALUE &&
						dist[u] + w < dist[v])
				{
					return;
				}
			}
		}
		
		printDistanceFromSource(dist);
	}

	@Test
	void test() {
		int V = 5, E = 10;
		DirectedGraph<String> directedGraph = new DirectedGraph<String>(V,E);
		
		Node<String> s = new Node<String>(0, "s");
		Node<String> t = new Node<String>(1, "t");
		Node<String> x = new Node<String>(2, "x");
		Node<String> y = new Node<String>(3, "y");
		Node<String> z = new Node<String>(4, "z");
		
		directedGraph.addEdge(s, t, 6);
		directedGraph.addEdge(s, y, 7);
		directedGraph.addEdge(t, y, 8);
		directedGraph.addEdge(t, z, -4);
		directedGraph.addEdge(t, x, 5);
		directedGraph.addEdge(x, t, -2);
		directedGraph.addEdge(y, x, -3);
		directedGraph.addEdge(y, z, 9);
		directedGraph.addEdge(z, s, 2);
		directedGraph.addEdge(z, x, 7);
		
		directedGraph.bellmanFord(0);
	}

Vertex 		Distance
s		0
t		2
x		4
y		7
z		-2

 

bellman-ford 알고리즘 시간복잡도

• O(NM) : N은 정점의 개수, M은 간선의 개수를 의미함

 

References

Source Code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/graph/graph10_bellmanford_shortestpath
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌