[이산구조]Dijkstra 알고리즘을 구현

소개글

Dijkstra 알고리즘을 구현하여 주어진 source로부터 destination까지의 최단 경로의 길이를 구하고자 한다. 각 입력자료에 대해 결과를 보여라.

1. 입력자료 양식
- 첫째 줄에는 총 vertex 개수(n)와 edge 개수(m)가 주어진다. Vertex index는 1부터 시작한다.
- 둘째 줄에는 source vertex index와 destination vertex index가 주어진다.
- 이어지는 m 줄에는 세 정수 i, j, w 가 주어지는데 i, j는 edge 양끝의 vertex index를 나타내고 w는 그 edge의 가중치를 나타낸다.

2. 각 입력 자료에 대해 source 로부터 destination까지의 최단 경로의 가중치 합을 출력하라. 가능하면 어떤 경로를 따라 가는지 그 경로도 다음과 같이 출력하라.
v10, v34, v21, ..., v43 // source index가 10, destination index가 43일 경우

컴파일 실행환경

비주얼 C++ 6.0

본문내용

#include <fstream.h>

#define MAX 400 // 입력 받는 파일 중 가장 큰 행렬의 크기

int shortestPath(int matrix[][MAX], int start, int end, int node); // 최단경로를 구하기 위한 함수 선언
void printPath(int path[], int start, int end); // 구간을 출력하는 함수의 선언

int main()
{
int node, edge, start, end;

ifstream fin;
fin.open ("최단거리.inp"); // ** 이 부분을 다른 파일로 변경 **


fin >> node >> edge;
fin >> start >> end;

int inputMatrix[MAX][MAX]; // 노드들을 행렬화

while(!fin.eof()) {
int x, y, z;
fin >> x >> y >> z;
inputMatrix[x-1][y-1] = z;
inputMatrix[y-1][x-1] = z;
}

참고 자료

없음