JAVA 최단경로

소개글

JAVA로 짠 최단 경로 입니다.
시작 점에서 제일 가까운 길을 선택하여 갑니다.

목차

문제 분석
소스
소스 분석
실행 결과

본문내용

최단 경로
최단 경로 구하기 그래프는 가중치를 가진 유향(방향성이 있는) 그래프를 전제한다.

문제분석
그래프에 대한 가장 기본적인 연산으로는 모든 정점과 변에 대한 처리를 하면서 순환 하는 것이 있다. 이를 위해서는 각 정점과 변을 단 한번만 조사하는 조직적인 절차가 필요한 데이터와 같이 그래프 전체를 조직적으로 조사하는 것을 그래프의 탐색(search)이라고 한다.



예를 들어, A에서 G까지의 최단 경로를 구하게 되면 먼저 2차원배열을 이용하여 길이 없는 곳은 길이 없다는 표시로 무한대인 99로 표시를 하여 나타내었다. A에서 연결된 C, B, D로 길을 선택 합니다. 그리고 C, B, D에서도 연결된 길이 있으면 찾아 가고, 갔던 길을 가지 않기 위해 Addcheck() 함수를 써서 방문한 곳인지 아닌지를 판단하게 된다. 대문자로 출력하기 위해 ASCII코드를 써서 출력을 하고, 최소의 비용인 경로로 선택하여 마지막에 Path_Out() 함수를 호출하여 A-> C-> D-> E-> G 라는 경로의 결과가 나오게 됩니다.

소스분석
#include<stdio.h>
#include <iostream.h>
const int Vertex_CNT = 7;

-> const 상수를 이용하여 총 Vertex 수를 7로 설정하였다.

class Graph
{
private:
struct V{
int Curr_weight;
int Before_vetex;
} Vertex[Vertex_CNT];

참고 자료

자바 프로그래밍