【データ構造】【図論】【最短経路】Dijkstraアルゴリズム

一、核心思想
       Primeアルゴリズムの考え方とほぼ同じであり,Primeアルゴリズムではlowcost配列を用いて生成ツリー間の最短距離に保存し,Dijkstraアルゴリズムではlowcost配列を用いて最初のノードに保存する最短経路である.
二、Primeアルゴリズムとの違い
       DijkstraアルゴリズムとPrimeアルゴリズムの類似度は99%に達し、Primeアルゴリズムと比較してDijkstraアルゴリズムには以下の点がある.
       1.最大の違いはlowcost配列のリフレッシュ方式が異なることであり、Primeアルゴリズムのリフレッシュ方式:
 

for(int j=1;j<=nodeCount;j++){
      if(lowcost[j]!=-1&&lowcost[j]>map[k][j]){
            lowcost[j]=map[k][j];
      }
}

        Dijkstraアルゴリズムのリフレッシュ方法:

for(int j=1;j<=nodeCount;j++){
	if(visited[j]==false&&lowcost[j]>(map[j][k]+minEdge)){
		lowcost[j]=map[j][k]+minEdge;
	}
}

 
        2.Primeアルゴリズムを使用してlowcost配列をフラグ配列として使用することができ、lowcost[i]=-1を使用して現在のノードが生成ツリーに追加されていることを識別することができるが、Dijkstraアルゴリズムではこのlowcost配列がノード1への最短パス値を保存しているため、ノードがアクセスされたかどうかを識別する識別配列visitedを再定義する必要がある(この配列はPrimeアルゴリズムで使用できますが、DijkstraアルゴリズムとPrimeアルゴリズムは1の違いしかありません)
        3.lowcost配列をリフレッシュする方式が変更されたため、「無限大」の標識であるmaxIntegerValueは再利用できなくなった(1<<31)−1、標識的な「無限大」として使用できる(1<<15)−1
三、コード実装(Java版)

import java.util.Scanner;

public class Dijkstra
{
	private static final int maxIntegerValue=(1<<15)-1;
	public static void main(String args[]){
		Scanner scanner=new Scanner(System.in);
		int[][] map=new int[101][101];
		boolean[] visited=new boolean[101];
		while(scanner.hasNext()){
			init(map,visited);
			int nodeCount=scanner.nextInt();
			int edgeCount=scanner.nextInt();
			for(int i=0;i<edgeCount;i++){
				int node1=scanner.nextInt();
				int node2=scanner.nextInt();
				int edgeValue=scanner.nextInt();
				if(map[node1][node2]>edgeValue){
					map[node1][node2]=edgeValue;
					map[node2][node1]=edgeValue;
				}
			}
			int shortestPathCost=dijkstra(nodeCount,map,visited);
			System.out.println(shortestPathCost);
		}
	}
	public static int dijkstra(int nodeCount,int[][] map,boolean[] visited){
		int lowcost[]=new int[101];
		lowcost[1]=0;
		visited[1]=true;
		for(int i=2;i<=nodeCount;i++){
			lowcost[i]=map[1][i];
		}
		for(int i=1;i<=nodeCount-1;i++){
			int minEdge=maxIntegerValue;
			int k=0;
			for(int j=1;j<=nodeCount;j++){
				if(visited[j]==false&&lowcost[j]<minEdge){
					k=j;
					minEdge=lowcost[j];
				}
			}
			visited[k]=true;
			for(int j=1;j<=nodeCount;j++){
				if(visited[j]==false&&lowcost[j]>(map[j][k]+minEdge)){
					lowcost[j]=map[j][k]+minEdge;
				}
			}
		}
		return lowcost[nodeCount];
	}
	public static void init(int[][] map,boolean[] visited){
		for(int i=0;i<map.length;i++){
			for(int j=0;j<map[i].length;j++){
				map[i][j]=maxIntegerValue;
			}
		}
		for(int i=0;i<visited.length;i++){
			visited[i]=false;
		}
	}
}

 四、テストデータ

  
6 10
1 2 6
2 5 3
5 6 6
6 4 2
4 1 5
3 1 1
3 2 5
3 5 6
3 6 4
3 4 5

  
5

 五、ACM
テーマリンク:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2143
ACコード:

import java.util.Scanner;

public class Main
{
	private static final int maxIntegerValue=(1<<15)-1;
	public static void main(String args[]){
		Scanner scanner=new Scanner(System.in);
		int[][] map=new int[101][101];
		boolean[] visited=new boolean[101];
		while(scanner.hasNext()){
			init(map,visited);
			int nodeCount=scanner.nextInt();
			int edgeCount=scanner.nextInt();
			for(int i=0;i<edgeCount;i++){
				int node1=scanner.nextInt();
				int node2=scanner.nextInt();
				int edgeValue=scanner.nextInt();
				if(map[node1][node2]>edgeValue){
					map[node1][node2]=edgeValue;
					map[node2][node1]=edgeValue;
				}
			}
			int shortestPathCost=dijkstra(nodeCount,map,visited);
			System.out.println(shortestPathCost);
		}
	}
	public static int dijkstra(int nodeCount,int[][] map,boolean[] visited){
		int lowcost[]=new int[101];
		lowcost[1]=0;
		visited[1]=true;
		for(int i=2;i<=nodeCount;i++){
			lowcost[i]=map[1][i];
		}
		for(int i=1;i<=nodeCount-1;i++){
			int minEdge=maxIntegerValue;
			int k=0;
			for(int j=1;j<=nodeCount;j++){
				if(visited[j]==false&&lowcost[j]<minEdge){
					k=j;
					minEdge=lowcost[j];
				}
			}
			visited[k]=true;
			for(int j=1;j<=nodeCount;j++){
				if(visited[j]==false&&lowcost[j]>(map[j][k]+minEdge)){
					lowcost[j]=map[j][k]+minEdge;
				}
			}
		}
		return lowcost[nodeCount];
	}
	public static void init(int[][] map,boolean[] visited){
		for(int i=0;i<map.length;i++){
			for(int j=0;j<map[i].length;j++){
				map[i][j]=maxIntegerValue;
			}
		}
		for(int i=0;i<visited.length;i++){
			visited[i]=false;
		}
	}
}
/*

*/ 



/**************************************
	Problem id	: SDUT OJ 2143 
	User name	: kdyzm 
	Result		: Accepted 
	Take Memory	: 90280K 
	Take Time	: 590MS 
	Submit Time	: 2016-01-24 13:49:42  
**************************************/