bellman ford 알고리즘 - dijkstra 알고리즘 다음은 bellman ford죠!

안녕하세요. 오늘은 bellman ford 알고리즘을 공부하려고 합니다.
bellman ford알고리즘은 시작 노드가 주어졌을 때 다른 모든 노드까지의 최단 경로를 구하는 알고리즘입니다.

자세히 살펴볼까요?

---

bellman ford 알고리즘부터는 과정이 길어져서 그림 예시를 준비하지 못했습니다.

바로 예제 코드를 살펴보도록 하겠습니다.

 

from dataclasses import dataclass
from typing import List


@dataclass
class Node:
    id: int
    is_visited: bool = False


@dataclass
class Edge:
    start_node: Node
    end_node: Node
    weight: float

    def get_weight(self) -> float:
        return self.weight

    def get_other_node(self, node_id: int) -> Node:
        if self.start_node.id == node_id:
            return self.end_node
        else:
            return self.start_node


@dataclass
class Graph:
    nodes: dict
    adjacent_edges: dict

    def get_node(self, node_id: int) -> Node:
        return self.nodes[node_id]

    def set_node_visited(self, node_id: int):
        self.nodes[node_id].is_visited = True

    def get_connected_nodes(self, node_id: int) -> List[Node]:
        adjacent_edges = self.adjacent_edges.get(node_id, [])
        return [edge.get_other_node(node_id) for edge in adjacent_edges]

    def get_adjacent_edges(self, node_id: int) -> List[Edge]:
        return self.adjacent_edges.get(node_id, [])


def bellmanford(graph, start_node_id):
    distances = {}
    path_map = {}
    for node in graph.nodes.values():
        distances[node.id] = float("inf")
        path_map[node.id] = None
    distances[start_node_id] = 0

    for _ in len(graph.nodes.values()) - 1:
    	for node in graph.nodes.values():
            for edge in graph.get_adjacent_edges(node.id):
                tmp = distances[edge.start_node.id] + edge.get_weight()
                if tmp < distances[edge.end_node.id]:
                    distances[edge.end_node.id] = tmp
                    path_map[edge.end_node.id] = edge.start_node.id

    return distances, path_map


if __name__ == "__main__":
    nodes = {}
    for i in range(6):
        nodes[i + 1] = Node(id=i + 1)

    adjacent_edges = {}
    adjacent_edges[1] = [Edge(start_node=nodes[1], end_node=nodes[2], weight=3)]
    adjacent_edges[1] += [Edge(start_node=nodes[1], end_node=nodes[3], weight=1)]
    adjacent_edges[2] = [Edge(start_node=nodes[2], end_node=nodes[4], weight=1)]
    adjacent_edges[2] += [Edge(start_node=nodes[2], end_node=nodes[5], weight=1)]
    adjacent_edges[2] += [Edge(start_node=nodes[2], end_node=nodes[6], weight=10)]
    adjacent_edges[3] = [Edge(start_node=nodes[3], end_node=nodes[4], weight=1)]
    adjacent_edges[5] = [Edge(start_node=nodes[5], end_node=nodes[6], weight=1)]

    graph = Graph(nodes=nodes, adjacent_edges=adjacent_edges)
    print(bellmanford(graph, 1))

예시로 사용한 그래프

실행 결과

실행 결과!

{1: None, 2: 1, 3: 1, 4: 2, 5: 2, 6: 5} 라고 실행 결과가 출력되었는데 해석하자면

키=목적지 정해진 노드, 값=키와 가장 가까운 노드 입니다.

 

실행 결과를 이용하여 6번 노드로 가장 가까운 경로를 찾아보면 다음과 같은 결과를 얻을 수 있습니다!

6 <= 5 <= 2 <= 1

---

bellman ford 알고리즘은 어떠셨나요?

다음에는 Floyd-Warshall 알고리즘을 공부하도록 해보겠습니다.

슬슬 단일 에이전트 경로 계획 알고리즘이 끝나가는 것 같네요 ㅎㅎ

 

더 공부하고 싶으신 내용이나 부족한 부분 알려주시면 보완하도록 하겠습니다.
감사합니다 👍