[파이썬/Python] 최단 경로 알고리즘 구현하기 ( Dijkstra / Bellman-ford / floyd-warshall )

최단 경로 알고리즘 구현하기 ( Dijkstra / Bellman-ford / floyd-warshall )

---

서론

최단 경로(Shortest Paths)는 두 정점 사이의 경로를 구성하는 모든 간선의 가중치 합이 최소인 경로를 말합니다.

최단 경로는 단일 시작점 최단 경로와 모든 쌍 최단 경로, 그리고 싸이클이 없는 그래프의 최단 경로로 구분됩니다.

 

단일 시작점 최단경로는 단일 시작점으로부터 각 정점에 이르는 최단경로를 구하고,

모든 쌍 최단경로는 모든 정점 쌍 사이의 최단경로를 모두 구합니다.

 

그 중에서도 단일 시작점 최단 경로인 다익스트라 알고리즘(Dijkstra Algorithm)과 벨만-포드 알고리즘(Bellman-ford Algorithm), 그리고 모든 쌍 최단경로인 플로이드-워샬 알고리즘(Floyd-Warshall Algorithm)에 대해 알아보려 합니다.

---

본론

shortest_path.py

import sys

class Graph:
    def __init__(self, adjacency_list, directed=False):
        self.adjacency_list = adjacency_list
        self.nodes = set()
        self.edges = set()
        self.num_nodes = 0
        self.num_edges = 0

        if directed:
            for node in adjacency_list:
                for adjacency_node in adjacency_list[node]:
                    weight = adjacency_list[node][adjacency_node]
                    self._add_node_and_edge(node, adjacency_node, weight)
        else:
            for node in adjacency_list:
                for adjacency_node in adjacency_list[node]:
                    edge_exist_conditions = [
                        (node, adjacency_node, adjacency_list[node][adjacency_node]) in self.edges,
                        (adjacency_node, node, adjacency_list[adjacency_node][node]) in self.edges,
                    ]
                    if any(edge_exist_conditions):
                        assert adjacency_list[node][adjacency_node] == adjacency_list[adjacency_node][node]
                    else:
                        weight = adjacency_list[node][adjacency_node]
                        self._add_node_and_edge(node, adjacency_node, weight)

    def _add_node_and_edge(self, s, d, weight):
        if s not in self.nodes:
            self.nodes.add(s)
            self.num_nodes += 1

        if d not in self.nodes:
            self.nodes.add(d)
            self.num_nodes += 1

        self.edges.add((s, d, weight))
        self.num_edges += 1


class ShortestPath:
    def __init__(self, graph):
        self.graph = graph
        self.dijkstra_tree = {}
        self.bellman_ford_tree = {}
        self.floyd_warshall_p = {}

    def print_solution(self, algorithm=None):
        if algorithm == "dijkstra":
            print("*** Dijkstra Solution ***")
            for v, u in self.dijkstra_tree.items():
                print("{0} -> {1}".format(u, v))
        elif algorithm == "bellman_ford":
            print("*** Bellman Ford Solution ***")
            for v, u in self.bellman_ford_tree.items():
                print("{0} -> {1}".format(u, v))
        else:
            raise ValueError()

    def print_floyd_warshall_path(self, q, r):
        if self.floyd_warshall_p[q][r] == 0:
            print(r, end=" ")
        else:
            self.print_floyd_warshall_path(q, self.floyd_warshall_p[q][r])
            self.print_floyd_warshall_path(self.floyd_warshall_p[q][r], r)

    def dijkstra(self, start_node='1'):
        S = set()
        d = {}
        for node in self.graph.nodes:
            d[node] = sys.maxsize
        d[start_node] = 0

        while len(S) != len(self.graph.nodes):
            V_minus_S = self.graph.nodes - S
            node = self.extract_min(V_minus_S, d)
            S.add(node) # 트리 내부 노드 집합에 최소 가중치 노드 추가
            for adj_node in graph.adjacency_list[node]: # 간선들에 대해
                if adj_node in V_minus_S and d[node] + graph.adjacency_list[node][adj_node] < d[adj_node]:
                    d[adj_node] = d[node] + graph.adjacency_list[node][adj_node] # 거리 저장
                    self.dijkstra_tree[adj_node] = node # 정점 저장

    def extract_min(self, V_minus_S, d):
        min = sys.maxsize
        selected_node = None

        for node in V_minus_S: # 트리 외부 노드들을 비교
            if d[node] < min: # d 값이 가장 작다면
                min = d[node] # d 값으로 저장
                selected_node = node # 최소 가중치 간선 노드

        return selected_node

    def bellman_ford(self, start_node='1'):
        d = {}
        for node in self.graph.nodes:
            d[node] = sys.maxsize
        d[start_node] = 0

        # i개의 간선으로 각 노드에 이르는 최단 경로 구성
        for i in range(1, len(self.graph.nodes)):
            for u, v, w in self.graph.edges: # 정점, 인접 정점, 가중치
                if d[u] + w < d[v]: # 더 짧다면
                    d[v] = d[u] + w # 최단 거리 저장
                    self.bellman_ford_tree[v] = u # 정점 저장
        
        return self.check_negative_cycle(d) # 음의 사이클 존재 여부 확인

    def check_negative_cycle(self, d):
        is_ok = True
        
        for u, v, w in self.graph.edges:
            if d[u] + w < d[v]: # 음의 사이클
                is_ok = False
        
        return is_ok

    def floyd_warshall(self):
        d = {}
        for node in self.graph.nodes:
            d[node] = {}
            self.floyd_warshall_p[node] = {}

        for i in self.graph.nodes:
            for j in self.graph.nodes:
                if j in self.graph.adjacency_list[i]:
                    d[i][j] = self.graph.adjacency_list[i][j]
                elif i == j:
                    d[i][j] = 0
                else:
                    d[i][j] = sys.maxsize

                self.floyd_warshall_p[i][j] = 0

        for k in self.graph.nodes: # 중간 정점 집합 {1, 2, ..., k}
            for i in self.graph.nodes: # i : 시작 정점
                for j in self.graph.nodes: # j : 마지막 정점
                    if d[i][k] + d[k][j] < d[i][j]: # 더 짧을 경우
                        self.floyd_warshall_p[i][j] = k # 정점 저장
                        d[i][j] = d[i][k] + d[k][j] # 경로 길이 저장

if __name__ == "__main__":
    #####################################################
    #####################################################
    ##             dijkstra algorithm test             ##
    #####################################################
    #####################################################
    dijkstra_adjacency_list = {
        '1': {'2': 8, '3': 9, '4': 11},
        '2': {'5': 10},
        '3': {'2': 6, '5': 2, '4': 3},
        '4': {'6': 9, '7': 8},
        '5': {'8': 2},
        '6': {'3': 12, '8': 5},
        '7': {'6': 7},
        '8': {'7': 4}
    }

    graph = Graph(adjacency_list=dijkstra_adjacency_list, directed=True)
    print("[Graph] number of nodes: {0}, number of edges: {1}".format(graph.num_nodes, graph.num_edges))
    print(graph.edges)
    sp = ShortestPath(graph=graph)
    sp.dijkstra(start_node='1')
    sp.print_solution(algorithm="dijkstra")

    print()

    #####################################################
    #####################################################
    ##         bellman-ford algorithm test - 1         ##
    #####################################################
    #####################################################
    bellman_ford_adjacency_list = {
        '1': {'2': 8, '3': 9, '4': 11},
        '2': {'5': 10},
        '3': {'2': -15, '5': 1, '4': 3},
        '4': {'6': 9, '7': 8},
        '5': {'8': 2},
        '6': {'3': 12, '8': 5},
        '7': {'6': -7},
        '8': {'7': 4}
    }

    graph = Graph(adjacency_list=bellman_ford_adjacency_list, directed=True)
    print("[Graph] number of nodes: {0}, number of edges: {1}".format(graph.num_nodes, graph.num_edges))
    print(graph.edges)
    sp = ShortestPath(graph=graph)
    is_ok = sp.bellman_ford(start_node='1')
    if is_ok:
        sp.print_solution(algorithm="bellman_ford")

    print()

    #####################################################
    #####################################################
    ##         bellman-ford algorithm test - 2         ##
    #####################################################
    #####################################################
    bellman_ford_adjacency_list_with_negative_cycle = {
        '1': {'2': 8, '3': 9, '4': 11},
        '2': {'5': 10},
        '3': {'2': -15, '5': 1, '4': 3},
        '4': {'6': 9, '7': 8},
        '5': {'8': 2},
        '6': {'3': -12, '8': 5},
        '7': {'6': -7},
        '8': {'7': 4}
    }

    graph = Graph(adjacency_list=bellman_ford_adjacency_list_with_negative_cycle, directed=True)
    print("[Graph] number of nodes: {0}, number of edges: {1}".format(graph.num_nodes, graph.num_edges))
    print(graph.edges)
    sp = ShortestPath(graph=graph)
    is_ok = sp.bellman_ford(start_node='1')
    if is_ok:
        sp.print_solution(algorithm="bellman_ford")
    else:
        print("음의 사이클 발견! 해 없음")
    
    print()

    #####################################################
    #####################################################
    ##           floyd-warshall algorithm test         ##
    #####################################################
    #####################################################
    floyd_warshall_adjacency_list = {
        '1': {'2': 1, '4': 1, '5': 5},
        '2': {'1': 9, '3': 3, '4': 2},
        '3': {'4': 4},
        '4': {'3': 2, '5': 3},
        '5': {'1': 3}
    }

    graph = Graph(adjacency_list=floyd_warshall_adjacency_list, directed=True)
    print("[Graph] number of nodes: {0}, number of edges: {1}".format(graph.num_nodes, graph.num_edges))
    print(graph.edges)
    sp = ShortestPath(graph=graph)
    is_ok = sp.floyd_warshall()

    #SOURCE: 2, DESTINATION: 1
    print('2', end=" ")
    sp.print_floyd_warshall_path(q='2', r='1')
    print()

    # SOURCE: 5, DESTINATION: 3
    print('5', end=" ")
    sp.print_floyd_warshall_path(q='5', r='3')
    print()

    # SOURCE: 2, DESTINATION: 4
    print('2', end=" ")
    sp.print_floyd_warshall_path(q='2', r='4')
    print()

 

[파이썬/Python] 최소 비용 신장 트리 알고리즘 구현하기 ( Prim / Kruskal )

그래프 클래스에 대한 설명은 이전 글에 적혀있습니다.

 

ShortestPath Class

class ShortestPath:
    def __init__(self, graph):
        self.graph = graph
        self.dijkstra_tree = {}
        self.bellman_ford_tree = {}
        self.floyd_warshall_p = {}

    def print_solution(self, algorithm=None):
        if algorithm == "dijkstra":
            print("*** Dijkstra Solution ***")
            for v, u in self.dijkstra_tree.items():
                print("{0} -> {1}".format(u, v))
        elif algorithm == "bellman_ford":
            print("*** Bellman Ford Solution ***")
            for v, u in self.bellman_ford_tree.items():
                print("{0} -> {1}".format(u, v))
        else:
            raise ValueError()

    def print_floyd_warshall_path(self, q, r):
        if self.floyd_warshall_p[q][r] == 0:
            print(r, end=" ")
        else:
            self.print_floyd_warshall_path(q, self.floyd_warshall_p[q][r])
            self.print_floyd_warshall_path(self.floyd_warshall_p[q][r], r)

    def dijkstra(self, start_node='1'):
        S = set()
        d = {}
        for node in self.graph.nodes:
            d[node] = sys.maxsize
        d[start_node] = 0

        while len(S) != len(self.graph.nodes):
            V_minus_S = self.graph.nodes - S
            node = self.extract_min(V_minus_S, d)
            S.add(node) # 트리 내부 노드 집합에 최소 가중치 노드 추가
            for adj_node in graph.adjacency_list[node]: # 간선들에 대해
                if adj_node in V_minus_S and d[node] + graph.adjacency_list[node][adj_node] < d[adj_node]:
                    d[adj_node] = d[node] + graph.adjacency_list[node][adj_node] # 거리 저장
                    self.dijkstra_tree[adj_node] = node # 정점 저장

    def extract_min(self, V_minus_S, d):
        min = sys.maxsize
        selected_node = None

        for node in V_minus_S: # 트리 외부 노드들을 비교
            if d[node] < min: # d 값이 가장 작다면
                min = d[node] # d 값으로 저장
                selected_node = node # 최소 가중치 간선 노드

        return selected_node

    def bellman_ford(self, start_node='1'):
        d = {}
        for node in self.graph.nodes:
            d[node] = sys.maxsize
        d[start_node] = 0

        # i개의 간선으로 각 노드에 이르는 최단 경로 구성
        for i in range(1, len(self.graph.nodes)):
            for u, v, w in self.graph.edges: # 정점, 인접 정점, 가중치
                if d[u] + w < d[v]: # 더 짧다면
                    d[v] = d[u] + w # 최단 거리 저장
                    self.bellman_ford_tree[v] = u # 정점 저장
        
        return self.check_negative_cycle(d) # 음의 사이클 존재 여부 확인

    def check_negative_cycle(self, d):
        is_ok = True
        
        for u, v, w in self.graph.edges:
            if d[u] + w < d[v]: # 음의 사이클
                is_ok = False
        
        return is_ok

    def floyd_warshall(self):
        d = {}
        for node in self.graph.nodes:
            d[node] = {}
            self.floyd_warshall_p[node] = {}

        for i in self.graph.nodes:
            for j in self.graph.nodes:
                if j in self.graph.adjacency_list[i]:
                    d[i][j] = self.graph.adjacency_list[i][j]
                elif i == j:
                    d[i][j] = 0
                else:
                    d[i][j] = sys.maxsize

                self.floyd_warshall_p[i][j] = 0

        for k in self.graph.nodes: # 중간 정점 집합 {1, 2, ..., k}
            for i in self.graph.nodes: # i : 시작 정점
                for j in self.graph.nodes: # j : 마지막 정점
                    if d[i][k] + d[k][j] < d[i][j]: # 더 짧을 경우
                        self.floyd_warshall_p[i][j] = k # 정점 저장
                        d[i][j] = d[i][k] + d[k][j] # 경로 길이 저장

다익스트라, 벨만포드, 플로이드 와샬 알고리즘과 그 출력에 대해 다루고 있습니다.

 

ShortestPath Class __init__:

def __init__(self, graph):
    self.graph = graph
    self.dijkstra_tree = {}
    self.bellman_ford_tree = {}
    self.floyd_warshall_p = {}

ShortestPath 클래스의 생성자입니다.

main으로부터 받아온 graph를 저장하고,

각 알고리즘의 최단 경로를 생성합니다.

 

ShortestPath Class print_solution function:

def print_solution(self, algorithm=None):
    if algorithm == "dijkstra":
        print("*** Dijkstra Solution ***")
        for v, u in self.dijkstra_tree.items():
            print("{0} -> {1}".format(u, v))
    elif algorithm == "bellman_ford":
        print("*** Bellman Ford Solution ***")
        for v, u in self.bellman_ford_tree.items():
            print("{0} -> {1}".format(u, v))
    else:
        raise ValueError()

ShortestPath 클래스의 출력입니다.

각 알고리즘을 통해 저장된 그래프를 출력합니다.

 

format

>>> print("{0} - {1}".format(u, v))
u - v

{} 를 활용하여 데이터의 종류에 상관없이 print문으로 표현이 가능합니다.

{}안에 숫자를 입력하여 몇 번째에 오는 데이터를 받을지를 결정합니다.

 

raise

>>> raise ValueError()
ValueError:

예외처리를 위해 사용합니다.

의도치 않은 결과가 나오는 것을 방지하기 위해, 의도하지 않은 조건이 나왔을 경우 raise를 통해 error를 출력합니다.

 

ShortestPath Class print_floyd_warshall_path function:

def print_floyd_warshall_path(self, q, r):
    if self.floyd_warshall_p[q][r] == 0:
        print(r, end=" ")
    else:
        self.print_floyd_warshall_path(q, self.floyd_warshall_p[q][r])
        self.print_floyd_warshall_path(self.floyd_warshall_p[q][r], r)

플로이드 와샬 알고리즘의 출력입니다.

값으로 0이 반환되면 해당 정점과 인접 정점 사이 거리가 최단 거리이므로 출력합니다.

계속 이동하며 최단거리를 찾으면서 이동하는 정점을 모두 출력합니다.

 

ShortestPath Class dijkstra function:

def dijkstra(self, start_node='1'):
    S = set()
    d = {}
    for node in self.graph.nodes:
        d[node] = sys.maxsize
    d[start_node] = 0
    while len(S) != len(self.graph.nodes):
        V_minus_S = self.graph.nodes - S
        node = self.extract_min(V_minus_S, d)
        S.add(node) # 트리 내부 노드 집합에 최소 가중치 노드 추가
        for adj_node in graph.adjacency_list[node]: # 간선들에 대해
            if adj_node in V_minus_S and d[node] + graph.adjacency_list[node][adj_node] < d[adj_node]:
                d[adj_node] = d[node] + graph.adjacency_list[node][adj_node] # 거리 저장
                self.dijkstra_tree[adj_node] = node # 정점 저장

기존 작성했던 프림 알고리즘과 매우 유사합니다. 프림 알고리즘과 다른 부분만 설명하겠습니다.

[파이썬/Python] 최소 비용 신장 트리 알고리즘 구현하기 ( Prim / Kruskal )

 

for adj_node in graph.adjacency_list[node]: # 간선들에 대해
    if adj_node in V_minus_S and d[node] + graph.adjacency_list[node][adj_node] < d[adj_node]:
        d[adj_node] = d[node] + graph.adjacency_list[node][adj_node] # 거리 저장
        self.dijkstra_tree[adj_node] = node # 정점 저장

다익스트라 알고리즘에서 d[node]는 이제까지 도달한 정점의 최단 경로이며, 이제까지 도달한 정점의 최단 경로(d[node])에서 그 정점의 인접 정점의 가중치(graph.adjacency_list[node][adj_node])를 더한 값이 과거 구했던 인접 정점의 최단 경로(d[adj_node])보다 짧다면 그 길이는 곧 인접 정점까지의 새로운 최단 경로가 될 것입니다.

 

ShortestPath Class bellman_ford function:

def bellman_ford(self, start_node='1'):
    d = {}
    
    for node in self.graph.nodes:
        d[node] = sys.maxsize
    
    d[start_node] = 0
    
    # i개의 간선으로 각 노드에 이르는 최단 경로 구성
    for i in range(1, len(self.graph.nodes)):
        for u, v, w in self.graph.edges: # 정점, 인접 정점, 가중치
            if d[u] + w < d[v]: # 더 짧다면
                d[v] = d[u] + w # 최단 거리 저장
                self.bellman_ford_tree[v] = u # 정점 저장
    
    return self.check_negative_cycle(d) # 음의 사이클 존재 여부 확인

벨만 포드 알고리즘 구현입니다.

 

# i개의 간선으로 각 노드에 이르는 최단 경로 구성
for i in range(1, len(self.graph.nodes)):
    for u, v, w in self.graph.edges: # 정점, 인접 정점, 가중치
        if d[u] + w < d[v]: # 더 짧다면
            d[v] = d[u] + w # 최단 거리 저장
            self.bellman_ford_tree[v] = u # 정점 저장

return self.check_negative_cycle(d) # 음의 사이클 존재 여부 확인

최대 n-1 개의 간선을 사용해서 최단 경로를 찾습니다.

 

u, v, w 에 각각 정점, 인접 정점, 가중치를 저장합니다.

 

이제까지 도달한 정점에서 찾은 최단 경로에 인접 정점까지의 가중치를 합한 경로(d[u] + w)가 기존에 존재한 인접 정점까지의 최단 경로(d[v])보다 더 짧다면, 그 경로가 최단 경로이므로 거리와 정점을 저장합니다.

 

마지막으로  음의 사이클을 확인하기 위해 반환할 때 check_negative_cycle 을 호출합니다.

 

ShortestPath Class check_negative_cycle function:

def check_negative_cycle(self, d):
    is_ok = True
    
    for u, v, w in self.graph.edges:
        if d[u] + w < d[v]: # 음의 사이클
            is_ok = False
    
    return is_ok

음의 사이클이 존재하는 그래프에 대하여 최단 경로를 산출하는 알고리즘은 존재할 수 없습니다.

따라서, 음의 사이클을 갖는 그래프는 벨만-포드 알고리즘을 적용할 수 없습니다.

 

벨만-포드 알고리즘은 반복 횟수를 n-1 개로 제한하였지만, 만약 그래프가 음의 사이클을 갖고 있고 시행 횟수를 제한하지 않고 무한대로 계속 반복하면 가중치가 음의 무한대를 가질 수 있습니다.

음의 사이클을 갖는 그래프의 벨만 포드 알고리즘 수행

 

검출 방법은 간단합니다.

for u, v, w in self.graph.edges:
    if d[u] + w < d[v]: # 음의 사이클
        is_ok = False

d에는 현재 벨만-포드 알고리즘을 수행한 후 각 정점들까지의 최단 거리가 저장되어있습니다.

 

여기서 벨만-포드 알고리즘의 같은 작업을 수행했을 때, 새로운 최단거리가 갱신된다면, 이는 시행을 무한히 반복한다면 음의 무한대로 수렴한다는 뜻이고, 즉 음의 사이클이 존재한다는 뜻입니다.

 

이를 is_ok 에 저장하고, main 에서 벨만-포드를 호출 시에 음의 사이클이 존재하지 않다면(is_ok = True) 출력을 허용하면 되겠습니다.

 

ShortestPath Class floyd_warshall function:

def floyd_warshall(self):
    d = {}
    
    for node in self.graph.nodes:
        d[node] = {}
        self.floyd_warshall_p[node] = {}
    
    for i in self.graph.nodes:
        for j in self.graph.nodes:
            if j in self.graph.adjacency_list[i]:
                d[i][j] = self.graph.adjacency_list[i][j]
            else:
                d[i][j] = sys.maxsize
            self.floyd_warshall_p[i][j] = 0
    
    for k in self.graph.nodes: # 중간 정점 집합 {1, 2, ..., k}
        for i in self.graph.nodes: # i : 시작 정점
            for j in self.graph.nodes: # j : 마지막 정점
                if d[i][k] + d[k][j] < d[i][j]: # 더 짧을 경우
                    self.floyd_warshall_p[i][j] = k # 정점 저장
                    d[i][j] = d[i][k] + d[k][j] # 경로 길이 저장

플로이드-와샬 알고리즘 구현입니다.

주어진 그래프를 W:인접행렬(adjacent matrix)로 표현합니다.

 

d = {}
for node in self.graph.nodes:
    d[node] = {}
    self.floyd_warshall_p[node] = {}
for i in self.graph.nodes:
    for j in self.graph.nodes:
        if j in self.graph.adjacency_list[i]:
            d[i][j] = self.graph.adjacency_list[i][j]
        elif i == j:
            d[i][j] = 0
        else:
            d[i][j] = sys.maxsize
        self.floyd_warshall_p[i][j] = 0

정점과 인접정점까지의 가중치를 d[i][j]에 저장합니다.

정점 본인은 0, 인접하고 있지 않으면 무한으로 초기화합니다.

elif i == j:
    d[i][j] = 0

만약 본인 정점에서 본인 정점까지 최단거리를 구하고 싶다면, 이 부분만 빼주시면 됩니다.

 

for k in self.graph.nodes: # 중간 정점 집합 {1, 2, ..., k}
    for i in self.graph.nodes: # i : 시작 정점
        for j in self.graph.nodes: # j : 마지막 정점
            if d[i][k] + d[k][j] < d[i][j]: # 더 짧을 경우
                self.floyd_warshall_p[i][j] = k # 정점 저장
                d[i][j] = d[i][k] + d[k][j] # 경로 길이 저장

모든 정점들을 탐색하면서 각 정점들 사이의 최단 경로를 탐색하고, 그 경로를 d[i][j]에 저장합니다.

 

정점 i 부터 정점 k 까지 거리와 k 부터 j 까지의 거리 합이 정점 i 부터 j 까지 거리 합보다 작다면, 최단거리이므로 경로를 저장해주고, p에는 k를 저장하여 해당 최단 거리로 가기 위해 중간에 거쳐가야할 정점을 저장해줍니다.

 

 

__main__:

if __name__ == "__main__":
    #####################################################
    #####################################################
    ##             dijkstra algorithm test             ##
    #####################################################
    #####################################################
    dijkstra_adjacency_list = {
        '1': {'2': 8, '3': 9, '4': 11},
        '2': {'5': 10},
        '3': {'2': 6, '5': 2, '4': 3},
        '4': {'6': 9, '7': 8},
        '5': {'8': 2},
        '6': {'3': 12, '8': 5},
        '7': {'6': 7},
        '8': {'7': 4}
    }

    graph = Graph(adjacency_list=dijkstra_adjacency_list, directed=True)
    print("[Graph] number of nodes: {0}, number of edges: {1}".format(graph.num_nodes, graph.num_edges))
    print(graph.edges)
    sp = ShortestPath(graph=graph)
    sp.dijkstra(start_node='1')
    sp.print_solution(algorithm="dijkstra")

    print()

    #####################################################
    #####################################################
    ##         bellman-ford algorithm test - 1         ##
    #####################################################
    #####################################################
    bellman_ford_adjacency_list = {
        '1': {'2': 8, '3': 9, '4': 11},
        '2': {'5': 10},
        '3': {'2': -15, '5': 1, '4': 3},
        '4': {'6': 9, '7': 8},
        '5': {'8': 2},
        '6': {'3': 12, '8': 5},
        '7': {'6': -7},
        '8': {'7': 4}
    }

    graph = Graph(adjacency_list=bellman_ford_adjacency_list, directed=True)
    print("[Graph] number of nodes: {0}, number of edges: {1}".format(graph.num_nodes, graph.num_edges))
    print(graph.edges)
    sp = ShortestPath(graph=graph)
    is_ok = sp.bellman_ford(start_node='1')
    if is_ok:
        sp.print_solution(algorithm="bellman_ford")

    print()

    #####################################################
    #####################################################
    ##         bellman-ford algorithm test - 2         ##
    #####################################################
    #####################################################
    bellman_ford_adjacency_list_with_negative_cycle = {
        '1': {'2': 8, '3': 9, '4': 11},
        '2': {'5': 10},
        '3': {'2': -15, '5': 1, '4': 3},
        '4': {'6': 9, '7': 8},
        '5': {'8': 2},
        '6': {'3': -12, '8': 5},
        '7': {'6': -7},
        '8': {'7': 4}
    }

    graph = Graph(adjacency_list=bellman_ford_adjacency_list_with_negative_cycle, directed=True)
    print("[Graph] number of nodes: {0}, number of edges: {1}".format(graph.num_nodes, graph.num_edges))
    print(graph.edges)
    sp = ShortestPath(graph=graph)
    is_ok = sp.bellman_ford(start_node='1')
    if is_ok:
        sp.print_solution(algorithm="bellman_ford")
    else:
        print("음의 사이클 발견! 해 없음")
    
    print()

    #####################################################
    #####################################################
    ##           floyd-warshall algorithm test         ##
    #####################################################
    #####################################################
    floyd_warshall_adjacency_list = {
        '1': {'2': 1, '4': 1, '5': 5},
        '2': {'1': 9, '3': 3, '4': 2},
        '3': {'4': 4},
        '4': {'3': 2, '5': 3},
        '5': {'1': 3}
    }

    graph = Graph(adjacency_list=floyd_warshall_adjacency_list, directed=True)
    print("[Graph] number of nodes: {0}, number of edges: {1}".format(graph.num_nodes, graph.num_edges))
    print(graph.edges)
    sp = ShortestPath(graph=graph)
    is_ok = sp.floyd_warshall()

    #SOURCE: 2, DESTINATION: 1
    print('2', end=" ")
    sp.print_floyd_warshall_path(q='2', r='1')
    print()

    # SOURCE: 5, DESTINATION: 3
    print('5', end=" ")
    sp.print_floyd_warshall_path(q='5', r='3')
    print()

    # SOURCE: 2, DESTINATION: 4
    print('2', end=" ")
    sp.print_floyd_warshall_path(q='2', r='4')
    print()

구현 파트입니다.

adjacency_list 는 정점, 인접 정점, 가중치를 차례로 딕셔너리 형태로 저장합니다.

 

벨만-포드 알고리즘에서는 음의 사이클일 경우 안내 메세지를 출력하도록 예외처리하였습니다.

---

결론

다익스트라 알고리즘 결과

 

벨만-포드 알고리즘 결과

 

벨만-포드 음의 사이클 발생

 

플로이드-와샬 알고리즘 결과

 

다익스트라, 벨만-포드, 플로이드-와샬 알고리즘에 따라서 최단 경로가 정상적으로 출력됨을 확인할 수 있습니다.

다익스트라 알고리즘으로 구한 최단 경로

 

벨만-포드 알고리즘으로 구한 최단 경로

 

플로이드-와샬 알고리즘에 수행된 그래프

 

다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘을 구현해보면서, 최단 경로(Shortest Paths)란 무엇인지 배우고 노드와 간선의 작성 방법과 이를 집합으로 표현하는 방법에 대해 자세히 알 수 있었습니다.