给定一个带权有向图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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/599033.html