クラシックアルゴリズムの図の最短経路(一):Dijkstraアルゴリズム

Dijkstraアルゴリズムは基本的に図の最短経路を説明する本ごとに1つのアルゴリズムがあると言えますが、基本的には原理と偽コードを話しています.今日は自分でJavaコードで実現して、ここに記録しました.
Dijkstraアルゴリズムは、いくつかの図の最短パス問題を解決するだけであり、これらの図は、重み値が負ではなく、有向図であるという条件を満たす必要がある.また,このアルゴリズムは単一源点最短経路,すなわち始点が固定されたある点のみを求めるのに適しているが,もちろん多源点最短経路を求めるには数回Dijkstraアルゴリズムを用いても求めることができる.
このアルゴリズムの原理は、まずソースポイントを処理し、ソースポイントから各ポイントまでの距離と前ノード情報を更新し、終了後にソースポイントを「処理済み」グループに配置し、「未処理」グループから出発点に最も近いポイントを探し、このポイントを通過した後に元のパスよりも短いパスがあるかどうかを見て、もしそうであれば、下距離と前ノード情報を更新し、いいえ、操作を行わない場合は、終了したらこの点も[処理済み](Processed)領域に入れ、すべての点が処理されるまでループします.次のコード:(最終的にパスを印刷するときにサボってパスを逆さに印刷しなかった)

package classic;

import java.util.Scanner;

public class Dijkstra {

	public static int start = 0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("        :");
		int V = sc.nextInt();//       
		int E = sc.nextInt();//       
		
		int[][] G = new int[V][V];//        
		int[] d = new int[V];//                  
		int[] pre = new int[V];//                    
		boolean[] used = new boolean[V];
		
		System.out.println("          、     :(     0  )");
		for(int i=0; i0 && d[i]>d[minIndex]+G[minIndex][i]){
					d[i] = d[minIndex]+G[minIndex][i];
					pre[i] = minIndex;
				}
			}
			cur++;
		}
		for(int i=0; i