컴퓨터 과학(Computer Science)/알고리즘(Algorithm)9 [알고리즘] 벨만-포드 알고리즘(Bellman-Ford Algorithm) 단일 출발지 최단 경로 Single Source Shortest PathSingle Source Shortest Path란, 말 그대로 하나의 출발지(Single Source)에서 시작한 최단 경로(Shortest Path)를 말합니다. 벨만-포드 알고리즘 Bellman-Ford AlgorithmBellman-Ford 알고리즘은, Dijkstra 알고리즘과 함께 가중치가 있고(Weighted) 방향이 있는(Directed) 그래프에서 Single Source Shortest Path(SSSP)을 구하는 알고리즘입니다. 가중치(Weight)가 0보다 크거나 같은 그래프만 풀 수 있는 Dijkstra 알고리즘과는 다르게, Bellman-Ford 알고리즘은 Negative Weighted Edge가 존재하는 .. 2023. 12. 1. [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 단일 출발지 최단 경로 Single Source Shortest PathSingle Source Shortest Path란, 말 그대로 하나의 출발지(Single Source)에서 시작한 최단 경로(Shortest Path)를 말합니다. 다익스트라 알고리즘 Dijkstra AlgorithmDijkstra 알고리즘은, 가중치가 있고(Weighted) 방향이 있는(Directed) 그래프에서 Single Source Shortest Path(SSSP)을 구하는 알고리즘입니다. 단, Dijkstra의 경우 가중치(Weight)가 0보다 크거나 같은 그래프만 풀 수 있습니다. Weight가 모든 범위, 즉 음수도 존재하는 그래프의 SSSP를 푸는 알고리즘으로는 벨만-포드(Bellman-Ford) 알고리즘이 있습.. 2023. 12. 1. [알고리즘] 위상 정렬(Topological Sort) Topological Sort는 기본적으로 DFS를 통해 구현합니다. DFS에 대한 내용은 아래 글에 있습니다.https://stevenkim1217.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-Python [알고리즘] 깊이 우선 탐색(DFS) - Python깊이 우선 탐색 Depth-First Search 깊이 우선 탐색(DFS)이란 그래프를 탐색하는 방법의 일종으로, root node에서 시작해서 깊이 방향(Depth)으로 확장하는 방식의 탐색을 말합니다. 깊이 방향이란, 한 노드stevenkim1217.tistory.com Topologic.. 2023. 12. 1. [알고리즘] DAG 최단 경로 문제(DAG Shortest Path Problem) Directed Acyclic Graph(DAG)DAG란 그래프 연결에 방향이 있고(Directed), 한 곳에서 순환이 발생하지 않는(Acyclic) 그래프(Graph)를 의미합니다.Edge RelaxationDAG Shortest Path 문제를 풀기 위해 Edge Relaxation 개념이 필요합니다. Edge Relaxation이란, 가중치가 있는 그래프(Weighted Graph)에서, 각 edge에 배정되어 있는 만큼의 가중치를 더해가며 탐색할 때, 더 나은(작은) 경로의 가중치가 있다면 그 값으로 update하는 것을 의미합니다. 말이 어렵게 느껴지는데 굉장히 쉬운 개념입니다. 결국 더 나은 대안으로 수정한다는 의미입니다. 그리고 앞으로 그래프에서 이 작업을 Relax라고 부릅니다.그림으로 .. 2023. 12. 1. [알고리즘] 깊이 우선 탐색(DFS) - Python 깊이 우선 탐색 Depth-First Search깊이 우선 탐색(DFS)이란 그래프를 탐색하는 방법의 일종으로, root node에서 시작해서 깊이 방향(Depth)으로 확장하는 방식의 탐색을 말합니다. 깊이 방향이란, 한 노드에서 시작해 여러개의 다음 노드로 펼쳐 나간 방식과 달리 한 노드에서 다음 하나의 노드로 들어가는 방향을 말합니다. 미로찾기의 예시를 떠올리면 DFS의 탐색 방향을 이해하기 쉽습니다.아래 그림1을 보겠습니다. DFS로 그래프를 탐색하면, 아래 그림의 보라색 경로와 같이 탐색하게 됩니다. S1에서 출발하여 a,b,c,d만 순회하고 끝이 납니다. 하지만 c와 f가 남았으므로 S3에서 다시 탐색을 시작합니다. 그리고 c에서 e와 f중 아직 방문하지 않은 f노드를 탐색함으로써 DFS가 끝.. 2023. 11. 10. 이전 1 2 다음
