WGraphDijkstra.h : Dijkstra알고리즘의 최단 경로 탐색 기능이 추가된 그래프

#pragma once

#ifndef ___WGraphDijkstra

#define ___WGraphDijkstra

//WGraphDijkstra.h : Dijkstra알고리즘의 최단 경로 탐색 기능이 추가된 그래프

#include "WGraph.h"

class WGraphDijkstra : public WGraph {

int dist[MAX_VTXS]; // 시작노드로부터의 최단경로 거리

bool found[MAX_VTXS]; // 방문한 정점 표시

public:

//방문하지 않은 정점들 중에서 최단경로 거리가 가장 작은 정점을 찾아 반환

int chooseVertex() {

int min = INF;

int minpos = -1;

for(int i=0;i<size;i++)

if (dist[i] < min && !found[i]) {

min = dist[i];

minpos = i;

}

return minpos;

}

//Dijkstra의 최단 경로 알고리즘 : start 정점에서 시작함.

void ShortestPath(int start) {

//초기화

for (int i = 0; i < size; i++) {

dist[i] = getEdge(start, i);

found[i] = false;

}

found[start] = true; // 시작노드 방문 표시

dist[start] = 0; // 최초 거리

int u = chooseVertex();

found[u] = true;

for (int w = 0; w < size; w++) {

if (found[w] == false)

if (dist[w] + getEdge(u, w) < dist[w])

dist[w] = dist[u] + getEdge(u, w);

}

}

void printDistance() { // dist 상태를 출력하는 함수

for (int i = 0; i < size; i++)

printf("%5d", dist[i]);

printf("\n");

}

};

#endif // !___WGraphDijkstra