그래프에서 최단경로구하기

소개

가중치방향 그래프에서 최단경로를 구합니다.
BellmanFord 알고리즘을 이용하여 한정점에서 각 정점으로의 최단경로를 구합니다.
구하는 과정도 출력하여 줍니다.
모든쌍의 최단경로를 구하여 줍니다.
구하는 과정도 출력하여 줍니다.

컴파일 실행환경

C++

본문내용

Ⅰ. BellmanFord 알고리즘을 이용한 한 정점에서 모든 정점으로의 최단경로 구하기

1. BellmanFord 알고리즘
한 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘으로 BellmanFord 알고리즘이 있다. 이는 Dijkstra 알고리즘에 의하는 경우 가중치가 음수인 경로가 있을 때 최단경로를 올바르게 구할 수 없던 오류를 수정한 알고리즘으로서, 선행하는 간선수를 늘려가면서 해당하는 정점으로의 비용을 계속해서 구해나가는 것이다. 이 알고리즘에 의하여 경로를 구하려면 선행하는 간선수를 알아야 하며, 이전에 해당 정점까지의 비용을 계산한 결과를 알아야한다. BellmanFord 알고리즘을 간단히 나타내면 아래와 같다.

for(int i=0; i<n; I++) dist[i] = length[v][i];
for(int k=2; k<=n-1;k++)
for(u!=v이고 최소한 하나의 진입 간선을 갖는 u에 대해)
for(그래프의 각 <i,v>에 대해)
if(dist[u] > dist[i] + length[i][u]) dist[u] = dist[i] + length[i][u];

2. 그래프의 경로 탐색을 위한 클래스 정의
특정 그래프의 최단경로를 탐색하기 위한 연산을 수행하기 위해서 클래스를 정의한다. 클래스에는 그래프를 저장하기 위한 2차원 배열을 선언하고, 각 경로로의 비용을 저장하기 위한 배열 dist를 선언한다. 그래프가 삽입될 배열 GraphArray의 value는 가중치를 나타낸다. 클래스의 정의는 아래와 같다.

class Graph {
private:
int GraphArray[7][7]; // 그래프를 가중치 인접 행렬로 표현.
int dist[7]; // 최단 경로를 구할때 이용할 배열.
public:
Graph();
void InsertCost(int i, int j, int n); // 그래프에 가중치를 삽입하는 함수.
};

InsertCost 함수는 가중치 인접배열에 각 정점간의 가중치를 입력해주는 역할을 한다. 인접배열에서 정점간 경로가 없는 경우는 1000을 입력하여 주고, 자신에 대하여는 0을 입력하여 준다.

참고자료

· 없음