【数据结构】【图论】【最短路径】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数组保存着到节点一的最短路径值，所以必须重新定义一个标识数组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  
**************************************/