StudyData Structure

최단 경로(Shortest path)

최단 경로

  • 음수 사이클은 안되지만 음수 가중치는 된다.
  • 방향 그래프(directed graph) - 방향 그래프는 대칭이 아니다.
  • 가중치 그래프(weighted graph)
  • 경로의 길이 = 에지 가중치의 합
최단 경로 알고리즘의 종류

  1. 하나의 출발점과 나머지 모든 목적지

    • Dijkstra Algorithm(음수 가중치가 없음)
    • Bellman-Ford Algorithm(음수 가중치가 있음)

  2. 모든 (출발점, 목적지) 쌍

    • Floyd-Warshall Algorithm

Dijkstra Algorithm

  • 탐욕 알고리즘(Greedy Algorithm)
  • 음수 가중치가 없다.
  • 최단 경로가 발견된 정점의 집합 S가 존재
  • 정점 v의 distance[v] : 출발 정점에서 집합 S에 있는 정점만 거쳐 v에 도달하는 경로의 길이
출처 : https://github.com/ythwork/CS

  • Relaxation of an edge

    • 출발 정점에서 정점 u까지 정점 v를 거치지 않고 오는 경로의 길이
      • distance[1]
    • 출발 정점에서 정점 v까지 먼저 온 후 정점 u로 가는 경로의 길이
      • distance[0] + w(v, u)
    • distance[1]와 distance[0] + w(v, u)를 비교
      • 더 작은 값으로 distance[1]을 변경
    • distance[1] > distance[0] + w(v, u)라면
      • distance[1] = distance[0] + w(v, u)

  • 인접 행렬을 만들어서 진행

    • 정점 i, j가 인접하면 에지의 가중치 입력
    • 정점 i, j가 인접하지 않으면 None 입력
Dijkstra Example
출처 : https://github.com/ythwork/CS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
import math

class ShortestPath:
    def __init__(self, src, dist, p):
        self.source = src
        self.distance = dist
        # predecessor
        self.p = p

    # 재귀 함수
    # dst : destination
    def print_path(self, dst):
        # 1. base case
        if self.source == dst:
            print(self.source, end="  ")
            return

        # 2. 언제 호출할 것인가?
        if self.p[dst] != None:
            self.print_path(self.p[dst])
        else:
            print("There is no path")
            return
        
        print(dst, end=" ")

class Graph:
    INF = 99999
    def __init__(self, vnum):
        self.adjacency_matrix = [[None for _ in range(vnum)] for _ in range(vnum)]
        self.vertex_num = vnum

    def insert_edge(self, u, v, w):
        self.adjacency_matrix[u][v] = w

    def find_min(self, distance, S):
        _min = Graph.INF
        min_v = None

        # for문으로 모든 vertex를 다 돌기 때문에 O(n)
        # min heap을 쓴다면(priority Queue) O(log(n))으로 성능을 높일 수 있다.
        for v in range(self.vertex_num):
            if v not in S and distance[v] < _min:
                _min = distance[v]
                min_v = v

        return min_v


    def dijkstra(self, src):
        S = set()
        # distance = [math.inf for _ in range(self.vertex_num)]
        # distance 값을 무한에 가깝게 입력
        distance = [Graph.INF for _ in range(self.vertex_num)]
        # p 값은 None을 입력
        p = [None for _ in range(self.vertex_num)]

        distance[src] = 0

        while len(S) < self.vertex_num:
            v = self.find_min(distance, S)
            S.add(v)
            
            # adj[v] 구하기
            for u in range(self.vertex_num):
                w = self.adjacency_matrix[v][u]

                # 핵심!!
                # w != None --> adj[v] 안에 u가 포함
                # u not in S -> u는 아직 S 안에 미포함
                # RELAXATION : if distance[u] > distance[v] + w then distance[u] = distance[v] + w
                if w != None and u not in S and distance[u] > distance[v] + w:
                    distance[u] = distance[v] + w
                    p[u] = v

        return ShortestPath(src, distance, p)

# test code
if __name__=="__main__":
    g = Graph(4)
    g.insert_edge(0, 1, 10)
    g.insert_edge(0, 2, 3)
    g.insert_edge(1, 3, 5)
    g.insert_edge(2, 1, 5)
    g.insert_edge(2, 3, 8)
    g.insert_edge(3, 1, 4)
    g.insert_edge(3, 2, 12)

    source=0
    dst = 3
    sp=g.dijkstra(source)
    for i in range(g.vertex_num):
        print('distance[{0}] : {1}, p[{0}] : {2}'.format(i, sp.distance[i], sp.p[i]))

    print(f"path from {source} to {dst}")
    # 최단 경로 구하기
    sp.print_path(dst)

Floyd-Warshall Algorithm

  • Dynamic Programming
  • 모든 (출발지, 목적지) 쌍에 대한 최단 경로
  • recursion
    • Ak[i][j] = min{Ak-1[i][j], Ak-1[i][k]+Ak-1[k][j]}
    • Ak[i][j]는 0~k 정점만 거쳐서 i에서 j까지 가는 최단 경로의 길이를 의미한다.
  • base case
    • A-1[i][j] = w(i, j)
    • A-1는 아무 노드도 거치지 않는 경로
      • 노드 i와 j가 인접하면 A-1[i][j] > 0
      • 노드 i와 j가 인접하지 않으면 A-1[i][j] = ∞
출처 : https://github.com/ythwork/CS
  • A1[0][3]이라면
    • 0, 1 정점만 거쳐서 0에서 3까지 가는 최단 경로의 길이
    • min{A0[0][3], A0[0][1]+A0[1][3]}
    • A0[0][3]
      • 0 정점만 거쳐서 3을 갈 수 없으므로 ∞
    • A0[0][1]+A0[1][3]
      • 10 + 20 = 30
    • 따라서 min{∞, 30} = 30
Floyd-Warshall Example
출처 : https://github.com/ythwork/CS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import copy

class ShortestPath:
    def __init__(self, A, path):
        self.A = A
        self.path = path

    # source와 destination을 모두 알아야 한다.
    # 둘 다 all source, all destination이므로
    def print_path(self, src, dst):
        print(src, end=" ")
        self.__print_sp(src, dst)
        print(dst, end=" ")

    def __print_sp(self, i, j):
        # base case
        if self.path[i][j] == None:
            return
        
        k = self.path[i][j]
        self.__print_sp(i, k)
        print(k, end=" ")
        self.__print_sp(k, j)


class Graph:
    INF = 99999
    def __init__(self, vnum):
        self.adjacency_matrix = [[Graph.INF for _ in range(vnum)] for _ in range(vnum)]
        for i in range(vnum):
            self.adjacency_matrix[i][i] = 0
        self.vertex_num = vnum

    def insert_edge(self, u, v, w):
        self.adjacency_matrix[u][v] = w

    # 재귀함수를 쓰지 않고 반복문으로 풀어나가는 것 = Dynamic Programming
    # 재귀함수보다 반복문이 성능이 좋고 빠르다.
    def floyd_warshall(self):
        # A^-1을 가져옴
        A = copy.deepcopy(self.adjacency_matrix)
        path = [[None for _ in range(self.vertex_num)] for _ in range(self.vertex_num)]

        for k in range(self.vertex_num):
            for i in range(self.vertex_num):
                for j in range(self.vertex_num):
                    # A^(k-1)[i][j]
                    # A^(k-1)[i][k] + A^(k-1)[k][j]
                    if A[i][j] > A[i][k] + A[k][j]:
                        A[i][j] = A[i][k] + A[k][j]
                        path[i][j] = k

        return ShortestPath(A, path)

# test code
if __name__=="__main__":
    g=Graph(6)
    g.insert_edge(0, 1, 5)
    g.insert_edge(0, 2, 7)
    g.insert_edge(0, 5, 9)
    g.insert_edge(1, 3, 4)
    g.insert_edge(1, 5, 2)
    g.insert_edge(2, 0, 8)
    g.insert_edge(2, 4, 6)
    g.insert_edge(3, 0, 6)
    g.insert_edge(3, 4, 2)
    g.insert_edge(3, 5, 3)
    g.insert_edge(4, 2, 3)
    g.insert_edge(4, 5, 10)
    g.insert_edge(5, 1, 7)
    g.insert_edge(5, 2, 4)

    source=2
    dest=3

    sp=g.floyd_warshall()

    # Adjacency matrix
    print("A mat")
    for i in range(g.vertex_num):
        for j in range(g.vertex_num):
            print("{}".format(sp.A[i][j]).rjust(4), end="")
        print()
    print()

    # path matrix
    # N일 경우 경유 지점이 없다는 의미
    print("path mat")
    for i in range(g.vertex_num):
        for j in range(g.vertex_num):
            if sp.path[i][j]==None:
                print("{} ".format("N").rjust(4), end="")
            else:
                print("{} ".format(sp.path[i][j]).rjust(4), end="")
        print()
    print()

    print("path from {} to {}".format(source, dest))
    # 최단 경로 구하기
    sp.print_path(source, dest)
Share