Algorithm Vision

그래프 알고리즘Advanced

플로이드-워셜 알고리즘

동적 프로그래밍을 사용하여 모든 정점 쌍 간의 최단 경로를 찾는 모든 쌍 최단 경로 알고리즘입니다. O(V³) 복잡도로 모든 정점을 중간 지점으로 고려합니다. 밀집 그래프, 추이적 폐쇄 계산, 그래프 지름 찾기에 필수적입니다. 네트워크 분석에서 깊은 응용을 가진 간단한 구현입니다.

#graph#all-pairs-shortest-paths#dynamic-programming#transitive-closure

Complexity Analysis

Time (Average)

O(V³)

Expected case performance

Space

O(V²)

Memory requirements

Time (Best)

O(V³)

Best case performance

Time (Worst)

O(V³)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 25•Section 25.2

Number of Vertices (3-6)

Adjacency Matrix (use ∞ for infinity)

Each row on a new line, comma-separated

Example Graphs:

How it works

• All-pairs shortest paths algorithm
• Uses dynamic programming approach
• O(V³) time, O(V²) space complexity
• Handles negative edge weights
• Formula: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

0

Swaps

0

Array Accesses

0

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in 그래프 알고리즘

너비 우선 탐색 (BFS)

그래프를 레벨별로 탐색하여 더 깊이 들어가기 전에 현재 깊이의 모든 정점을 방문합니다. 큐를 사용하며 가중치가 없는 그래프에서 최단 경로를 찾는 데 이상적입니다. 미로 해결, 소셜 네트워크 분석, 노드 간 연결 찾기 등의 응용 프로그램이 있습니다.

깊이 우선 탐색 (DFS)

역추적하기 전에 각 경로를 따라 가능한 한 깊이 들어가서 그래프를 탐색합니다. 스택이나 재귀를 사용하여 구현되어 재귀적 문제에 자연스럽습니다. 경로 찾기, 순환 감지, 위상 정렬, 미로 생성에 사용됩니다.

다익스트라 알고리즘

가중치가 있는 그래프에서 단일 소스 정점에서 다른 모든 정점까지의 최단 경로를 찾습니다. GPS 내비게이션 시스템과 네트워크 라우팅 프로토콜을 지원합니다. 우선순위 큐를 사용하는 탐욕적 접근법으로 음수가 아닌 가중치에 효율적으로 작동합니다.

O((V + E) log V)

graphshortest-path

Back to 그래프 알고리즘

Floyd-Warshall Algorithm - Algorithm Vision