다익스트라 알고리즘과 벨만포드 알고리즘 구현

소개글

다익스트라 알고리즘과 벨만포드 알고리즘 구현에 대한 보고서 자료입니다.

목차

1. 문제제기
　(1) 다익스트라 알고리즘
　(2) 벨만포드 알고리즘

2. 문제분석 & 문제해결
　(1) 다익스트라 알고리즘
　(2) 벨만포드 알고리즘

3. 프로그래밍 소스

4. 입력형식
　예시)

5. 결과화면

5. 느낀점

본문내용

iVertexCount-1;i++)
{
count = Queue->Count;//큐의 원소 갯수
for(j=0;j {//이전 loop에서 enqueue한 횟수만큼 pop
Node* Popped = LQ_Dequeue( &Queue );//큐에서 노드를 꺼낸다. (BFS방식)
CurrentVertex = Popped->V; //방금 꺼낸 정점을 현재 노드로 설정한다.
Fringes[CurrentVertex->Index] = CurrentVertex;//그 정점의 이웃정점들을 연결한다.
CurrentEdge = CurrentVertex->AdjacencyList;//그 정점과의 이웃정점사이의 엣지들을 현재 엣지로 설정한다.
while ( CurrentEdge != NULL )//연결된 모든 엣지들에 대해
{
Vertex* TargetVertex = CurrentEdge->Target;//Dest정점을 설정하고
LQ_Enqueue( &Queue, LQ_CreateNode( TargetVertex ) );//그 정점을 큐에 넣는다(나중에 BFS로 다시 이 정점부터 탐색하기 위함)
if (Weights[CurrentVertex->Index] + CurrentEdge->Weight < Weights[TargetVertex->Index] )//가중치가 더 낮은 경우를 발견하면
{
Precedences[TargetVertex->Index] = CurrentEdge->From;//더 짧은 값으로 교체한다.
Weights[TargetVertex->Index] =
Weights[CurrentVertex->Index] + CurrentEdge->Weight;
}
CurrentEdge = CurrentEdge->Next;//연결된 다음 엣지로..
}
}
}
//음의 사이클을 찾는다.
CurrentVertex = StartVertex;//첫 정점부터
while ( CurrentVertex != NULL )//모든 정점을 탐색한다
{
if ( (CurrentEdge = CurrentVertex->AdjacencyList) == NULL )
{
CurrentVertex = CurrentVertex->Next;
continue;
}
while ( CurrentEdge != NULL )
{
Vertex* TargetVertex = CurrentEdge->Target;
if (Weights[CurrentVertex->Index] + CurrentEdge->Weight < Weights[TargetVertex->Index] )
//이미 생성된 경로가 최단경로인데, 이보다 더 짧은 경로가 발견되면 음의 사이클이다.
{
// printf("음의 사이클이 존재함\n");
return 0;
}
CurrentEdge = CurrentEdge->Next;//다음 엣지로
}
CurrentVertex = CurrentVertex->Next;//다음 정점으로
}
for ( i=0; iVertexCount; i++ )// 생성된 최단경로를 토대로, MST를 만든다.
{
int FromIndex, ToIndex;
if ( Precedences[i] == NULL )
continue;
FromIndex = Precedences[i]->Index;
ToIndex = i;
AddEdge( ShortestPathVertices[FromIndex],//MST그래프에 엣지를 추가한다.
CreateEdge(
ShortestPathVertices[FromIndex],
ShortestPathVertices[ToIndex],
Weights[i] ) );
ShortestPath->EdgeCount++;
}
while(Queue->Count != 0)//큐에 있는 남은 원소를 모두 제거하고
LQ_Dequeue(&Queue);
LQ_DestroyQueue( Queue ); //큐 소멸
free( Fringes );
free( Precedences );
free( ShortestPathVertices );
free( Weights );
return 1;
}
4. 입력형식 :
input.txt
11
a 4 b 4 e 3 d 2 c 1
b 2 a 4 f 4
c 2 a 1 d 2
d 4 a 2 c 2 f 4 g 4
e 2 a 3 f 4
f 5 b 4 e 4 d 4 j 2 k 4
g 4 d 4 h 3 i 3 j 4
h 2 g 3 i 2
i 3 g 3 h 2 j 2
j 4 g 4 i 2 f 2 k 1
k 2 f 4 j 1
예시)
9
b 3 a 35 c 126 f 150
a 1 e 247
c 3 d 117 g 220 f 162
d 0
e 1 h 98
f 3 e 82 g 154 h 120
g 1 i 106
h 0
i 0
7
a 3 b 6 c 5 d 5
b 1 e -1
c 2 b -2 e 1
d 2 c -2 f -1
e 1 g 3
f 1 g 3
g 0
//음의 사이클
3
a 1 b 1
b 2 a -2 c 1
c 0
8
a 3 b 8 c 9 d 11
b 1 e 10
c 3 b -15 e 1 d 3
d 1 g 8
e 1 h 2
f 2 c 12 h 5
g 1 f -7
h 1 g 4
5. 결과화면 :
5. 느낀점 :
저는 사실 1학년 2학기때 컴퓨터프로그래밍2 과목에서 팀 프로젝트로 다익스트라 알고리즘을 사용한 서울 지하철 최단경로 탐색 프로그램을 구현한 적이 있었습니다. 사실 그때는 알고리즘의 정확한 개념은 알지 못하고 그냥 위키의 소스를 사용해서 어떻게 구현할 것 인가하는 방법을 택했습니다. 그래서인지 이번 과제는 굉장히 흥미가 있었습니다. 또 지난 학기에 배운 컴퓨터네트워크 과목에서 라우팅 알고리즘에 대해 배웠는데, 실제로 그 알고리즘들을 코딩해보니 매우 흥미 있었습니다.
대부분의 시중에 나와있는 알고리즘 관련 서적이나 인터넷에는 모두 배열로 구현한 그래프에 대한 최단 경로탐색법만 존재하였습니다. 그래서 저는 링크드리스트를 사용한 인접리스트 표현법으로 최단경로신장트리를 만들고, 그 신장트리를 토대로 경로를 찾아서 출력하는 함수를 따로 정의하였습니다. 소스코드를 참조해주시기 바랍니다.
한 학기동안 수고하셨습니다.

키워드

다익스트라,   벨만 포드,   최단 경로,   알고리즘,   Dijkstra,   Bellman-Ford,   다익스트라 알고리즘,   벨만포드 알고리즘