c/c++语言开发共享Dijkstra贪心算法求单源最短路径

 给定一个带权有向图G=（V,E），其中每条边的权是一个非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。

Dijkstra算法是解单源最短路径的贪心算法。《算法设计与分析》一书中给出的代码存在问题，其中一个明显的错误就是用==对浮点数进行相等判断。对书中的代码进行修订后实现如下：

 public static void dijkstra(int sourcePoint, float[][] weightMatrix, float[] distance, int[] previousPoints) { 		// the numbers of points; 		int pointNumber = distance.length; 		if (sourcePoint <0 || sourcePoint >= pointNumber) { 			// the sourcePoint exceed the valid point index; 			return ; 		} 		 		boolean[] selectedPoints = new boolean[pointNumber]; 		 		// initialize three array: 		// 1. initialize the array of distance  from source point to each  point; 		// 2. initialize the array of selected points  with false; 		// 3. initialize the array of previous points with 0; 		for(int i=0; i< pointNumber; i++) { 			distance[i] = weightMatrix[sourcePoint][i]; 			selectedPoints[i] = false; 			if (Math.abs(distance[i]- Float.MAX_VALUE) < 0.0001f ) { 				previousPoints[i] = -1; 			}else { 				// there is a line link between sourcePoint and currentPoint; 				previousPoints[i] = sourcePoint; 			} 		} 		 		// step 1: put source point into selected set; 		selectedPoints[sourcePoint] = true; 		 		 		for(int i=0; i< pointNumber; i++) { 			// a temp variable that store the shortest distance; initialize value with float max. 			float tempShortestDist = Float.MAX_VALUE; 			 		    // this variable store next candidate point which has shortest distance; 			int candidatePoint = sourcePoint; 			// step 2: find a point which has shortest distance; 			// traverse the set of All Points minus Selected Points and calculate the shorted distance from source to each point 			for (int j=0; j<pointNumber; j++) { 				if(!selectedPoints[j] && distance[j] < tempShortestDist) { 					candidatePoint = j; 					tempShortestDist = distance[j]; 				} 			} 			 			//  step3 : add the candidate point to selected set; 			selectedPoints[candidatePoint] = true; 			 			// step 4: calculate the distance of  SPECIAL Path that start from candidatePoint to each point; 			for (int j=0; j<pointNumber; j++) { 				if (!selectedPoints[j] && weightMatrix[candidatePoint][j] < Float.MAX_VALUE) { 					// point j is not in selected points set and there is a line between point candidatePoint and j; 					float newDistance = distance[candidatePoint]  + weightMatrix[candidatePoint][j]; 					if (newDistance < distance[j]) { 						// the distance from cadidatePoint is less than before(start from previous point); 						distance[j] = newDistance; 						previousPoints[j] = candidatePoint; 					} 				} 			}// end of for 		}// end of for 	}

c/c++开发分享Dijkstra贪心算法求单源最短路径地址：https://blog.csdn.net/redredxcar/article/details/85929100