Algorithm/Concepts18 최단 경로 (플로이드-와샬(Floyd-Warshall)) 목차 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘은 모두 그래프에서 최단 경로를 찾는 알고리즘입니다. 각 알고리즘은 특정한 조건에서 사용됩니다. 다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 없는 경우) 벨만-포드 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 존재하는 경우. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 플로이드-와샬 : 모든 노드쌍에 대한 최단경로를 모두 찾을 때(음의 가중치가 없어도 있어도 모두 사용가능. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 플로이드-와샬(Floyd-Warshall) 플로이드-와샬 알고리즘은 모든 정점 간의 최단 경.. 2024. 2. 15. 최단 경로 (벨만-포드(Bellman-Ford)) 목차 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘은 모두 그래프에서 최단 경로를 찾는 알고리즘입니다. 각 알고리즘은 특정한 조건에서 사용됩니다. 다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 없는 경우) 벨만-포드 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 존재하는 경우. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 플로이드-와샬 : 모든 노드쌍에 대한 최단경로를 모두 찾을 때(음의 가중치가 없어도 있어도 모두 사용가능. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 벨만-포드(Bellman-Ford) 벨만-포드 알고리즘은 간선이 음의 가중치를 가질 때, 하.. 2024. 2. 14. 최단 경로 (다익스트라(Dijkstra)) 목차 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘은 모두 그래프에서 최단 경로를 찾는 알고리즘입니다. 각 알고리즘은 특정한 조건에서 사용됩니다. 다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 없는 경우) 벨만-포드 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 존재하는 경우. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 플로이드-와샬 : 모든 노드쌍에 대한 최단경로를 모두 찾을 때(음의 가중치가 없어도 있어도 모두 사용가능. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 다익스트라(Dijkstra) 다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의.. 2023. 10. 16. BFS(Breadth-First Search, 너비 우선 탐색), DFS(Depth-First Search, 깊이 우선 탐색) 목차 BFS(Breadth-First Search, 너비 우선 탐색) BFS는 그래프나 트리에서 가장 인접한 노드부터 방문하며, 더 이상 인접한 노드가 없을 때 다음 레벨의 노드들을 방문하는 방식으로 탐색하는 알고리즘입니다. BFS는 주로 큐를 사용하여 구현합니다. BFS의 시간복잡도는 O(V+E)가 됩니다. (V:노드수, E:간선수) 각 노드와 그와 연결된 간선을 한 번씩 확인하므로 위와 같은 시간복잡도를 가지게 됩니다. 코드 from collections import deque def bfs(graph,start,visited): q=deque([start]) # 현재 노드를 방문 처리 visited[start]=True # 큐가 빌 때까지 반복 while q: # 큐에서 하나의 원소를 뽑아 출력 v.. 2023. 10. 16. 이전 1 2 3 4 5 다음
