[perl] 최단 경로 알고리즘
최단 경로 알고리즘은 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘을 말합니다. 이 글에서는 대표적인 최단 경로 알고리즘들을 살펴보고, Perl을 사용하여 간단한 예제를 통해 구현해보겠습니다.
목차
다익스트라 알고리즘
다익스트라 알고리즘은 음이 아닌 가중치를 가진 그래프에서 최단 경로를 찾는 알고리즘으로, 가장 짧은 경로부터 탐색해 나가는 방식으로 동작합니다. Perl에서는 Graph::Dijkstra 모듈을 사용하여 다익스트라 알고리즘을 구현할 수 있습니다.
use Graph::Dijkstra;
my $graph = Graph::Dijkstra->new();
# 그래프 정의
$graph->add_edge('A', 'B', 1);
$graph->add_edge('B', 'C', 2);
$graph->add_edge('A', 'C', 4);
# 최단 경로 계산
my $shortest_path = $graph->shortest_path('A', 'C');
print "최단 경로: " . join(' -> ', @$shortest_path) . "\n";
위 예제는 Perl을 사용하여 다익스트라 알고리즘을 적용한 코드입니다. 입력 그래프를 정의하고, shortest_path 메서드를 통해 최단 경로를 찾고 출력하는 내용을 담고 있습니다.
벨만-포드 알고리즘
벨만-포드 알고리즘은 음의 가중치를 가진 그래프에서도 최단 경로를 찾을 수 있는 알고리즘이며, 음수 사이클의 여부도 감지할 수 있습니다. Perl에서는 Graph::Dijkstra 모듈을 사용하여 벨만-포드 알고리즘을 구현할 수 있습니다.
use Graph::Dijkstra;
my $graph = Graph::Dijkstra->new();
# 그래프 정의
$graph->add_weighted_edge('A', 'B', 1);
$graph->add_weighted_edge('B', 'C', 2);
$graph->add_weighted_edge('A', 'C', -4);
# 최단 경로 계산
my $shortest_path = $graph->shortest_path('A', 'C');
print "최단 경로: " . join(' -> ', @$shortest_path) . "\n";
위 예제는 Perl을 사용하여 벨만-포드 알고리즘을 적용한 코드입니다. 입력 그래프를 정의하고, shortest_path 메서드를 통해 최단 경로를 찾고 출력하는 내용을 담고 있습니다.
최단 경로 알고리즘은 그래프 이론에서 매우 중요한 주제이며, Perl을 통해 두 가지 유명한 알고리즘인 다익스트라 알고리즘과 벨만-포드 알고리즘을 구현하는 방법에 대해 알아보았습니다.