[자료구조] Shortest Path 최단 경로 알고리즘, Dijkstra Algorithm 다익스트라 알고리즘

Dijkstra 다익스트라 알고리즘 : 최단 경로 / 최소 비용으로 가는 알고리즘, 양의 간선 사용

​

출처 위키백과

​

*중요한 부분:

dist[i] = dist[i] < dist[이전방문노드] + edges[이전방문노드][i] ? dist[i] : dist[이전방문노드] + edges[이전방문노드][i]

=> i의 최소 경로 갱신.

'이전 방문노드의 최소 경로 + 이전 방문노드에서 i로 가는 비용' 과 현재 저장되어 있는 i의 최소 경로 중 더 적은 값을 택하여 i의 최소 경로로 설정.

​

나는 좀 이상하게 푼 것 같지만.. 최소 힙을 사용하면 더 수월하게 풀 수 있다.

갈 수 있는 경로들 중 가장 적은 값을 빼내서 저장하는 ?

public static void Dijkstra(String vertex[], int edges[][], int startv, int endv) {
		int dist[] = new int[vertex.length + 1]; // vertex는 1부터 시작하므로
		boolean visit[] = new boolean[vertex.length + 1];
		int resultver[] = new int[vertex.length];
		int resultindex = 0;
		for (int i = 1; i <= vertex.length; i++) {
			dist[i] = edges[startv][i]; // dist 초기화
			visit[i] = false;
		}
		visit[startv] = true;
		resultver[resultindex++] = startv;
		print(dist, visit);

		int nowver = startv;

		while (nowver != endv) {
			int next = 0;
			int nextver = 0;

			for (int j = 1; j <= vertex.length; j++) {
				if (visit[j] == false) {
					if (next == 0 && edges[nowver][j] != 0) {
						next = edges[nowver][j]; // next에 첫 값 저장
						nextver = j;
					} else {
						if (edges[nowver][j] != 0 && next > edges[nowver][j]) {
							next = edges[nowver][j];
							nextver = j;
						}
					}
				}
			}
			visit[nextver] = true;
			resultver[resultindex++] = nextver;
			dist = calDist(edges, visit, dist, nextver);
			print(dist, visit);

			nowver = nextver;
		}

		if (visit[endv] == false) {
			System.out.println("no where to go " + endv);
		} else {
			for (int i : resultver)
				System.out.print(i);
		}
	}

	public static int[] calDist(int edges[][], boolean visit[], int dist[], int ver) { // 지금 방문하는 점

		for (int i = 1; i < visit.length; i++) {
			if (edges[ver][i] != 0) {
				dist[i] = dist[i] < dist[ver] + edges[ver][i] ? dist[i] : dist[ver] + edges[ver][i];
			}
		}

		return dist;
	}

	public static void print(int dist[], boolean visit[]) {
		for (int i : dist)
			System.out.print(i + " ");
		for (boolean i : visit)
			System.out.print(i + " ");

		System.out.println();
	}
}