对于单源最短路径问题,可以利用贪心策略求解,其经典算法便是Dijkstra算法。首先找出与v0点最邻近点的最短路径,然后找出与v0点第二近顶点的最短路径,直到找到最后一个点与v0的最短路径。
实现Dijkstra算法可以和prim算法类似,需要构造2个集合s1,s2。其中s1是当前搜索到的最短路径顶点集,s2是剩下的带求解的点集。每一次搜索都会将s2中的点与最后加入到s1的点进行权值更新操作,一旦发现有s1到s2的更短的路径,就更新目前的距离集合,并且将最短距离对应的那个点加入到s1中,并从s2中删除。
Dijkstra算法的时间复杂度是O(n^2)。
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* 单源最短路径的Dijkstra算法实现
* @author ql_math
*
*/
public class DijkstraShortestPath {
/**最短路径的连接*/
private double[] shortestPathArray;
private int pointsNum;
/**
* Dijkstra算法计算单源最短路径
* @param pIndex
* @param graphicArray
* @return
*/
public double[] calculateShortestPath(int pIndex, double[][] graphicArray)
{
SimpleGraphics graph=new SimpleGraphics(graphicArray);
pointsNum=graph.getPSize();//顶点数目
List<Integer> curFoundList=new LinkedList<Integer>();//当前找到的点集合
curFoundList.add(pIndex);
List<Integer> midList=new LinkedList<Integer>();//待查找点集
shortestPathArray=new double[pointsNum];//获得与当前点连接的点集合
initShortestPath(midList,pIndex);//待查找点集
int set_num=1;
while(set_num<=pointsNum)
{
int cur_shortest_index=calculateP2PShortestPath(graph,curFoundList,midList);//找出与当前点连接的点距最小值的点
curFoundList.add(cur_shortest_index);
midList.remove(new Integer(cur_shortest_index));
set_num++;
}
return shortestPathArray;
}
private int calculateP2PShortestPath(SimpleGraphics graph, List<Integer> curFoundList, List<Integer> midList) {
int compareNode=((LinkedList<Integer>)curFoundList).getLast();
double[] array=graph.getAdjacencyPoints(compareNode);
double min=Double.MAX_VALUE;
int index=0;
for(int i=0;i<pointsNum;i++)
{
double newLen=shortestPathArray[compareNode]+array[i];
if(newLen<shortestPathArray[i]&&midList.contains(i))
shortestPathArray[i]=newLen;
}
for(int i=0;i<pointsNum;i++)
{
if(shortestPathArray[i]<min&&midList.contains(i))
{
index=i;
min=shortestPathArray[i];
}
}
return index;
}
/**
* 初始化
* @param n
* @param index
*/
private void initShortestPath(List<Integer> list, int index) {
for(int i=0;i<pointsNum;i++)
{
if(i!=index)
{
list.add(i);
shortestPathArray[i]=Double.MAX_VALUE;
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
DijkstraShortestPath dj=new DijkstraShortestPath();
double[][] graphicArray={{0,1,6,Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE},
{1,0,3,4,6,Double.MAX_VALUE},{6,3,0,2,2,Double.MAX_VALUE},
{Double.MAX_VALUE,4,2,0,2,3},{Double.MAX_VALUE,6,2,2,0,4},{Double.MAX_VALUE,Double.MAX_VALUE,Double.MAX_VALUE,3,4,0}};
System.out.println("最短路径:"+Arrays.toString(dj.calculateShortestPath(0,graphicArray)));
}
}
分享到:
相关推荐
用C++实现的贪心算法 Dijkstra 单源最短路径,并包含大量的注释,对理解程序很有帮助
本设计以VC++6.0作为程序开发环境,C语言作为程序开发语言,详细介绍了最短路径的求解算法及其...请用C/C++语言的结构体、指针、数据结构等基础知识,编写程序实现图的结构定义、图的存储,以及求解单源点最短路径。
Dijkstra算法可用于求解图中某源点到其余各顶点的最短路径。假设G={V,{E}}是含有n个顶点的有向图,以该图中顶点v为源点,使用Dijkstra算法求顶点v到图中其余各顶点的最短路径的基本思想如下: 使用集合S记录已...
一般背包问题的贪心算法 Dijkstra算法求解单源最短路径问题 N皇后问题 Prim算法 Kruskal算法代码
成功应用贪心算法的问题包括霍夫曼编码、最小生成树(如Kruskal算法和Prim算法)和单源最短路径(如Dijkstra算法)等。选择贪心算法时,重要的是验证贪心选择性质和最优子结构性质,确保每步做出的局部最优选择可以...
经典Dijkstra算法是一种贪心算法,根据路径长度递增次序找到最短路径,通常用于解决单源最短路的问题。Dijkstra算法的基本思想是:首先根据原有路径图,初始化源点到与其相邻节点的距离,选出与源点最短距离的节点...
标号法求解单源点最短路径: B.Floyed算法求解所有顶点对之间的最短路径: C. Dijkstra 算法: 3.计算图的传递闭包 4.无向图的连通分量 A.深度优先 B 宽度优先(种子染色法) 5.关键路径 6.拓扑排序 7.回路...
24.3 Dijkstra算法 24.4 差分约束和最短路径 24.5 最短路径性质的证明 思考题 本章注记 第25章 所有结点对的最短路径问题 25.1 最短路径和矩阵乘法 25.2 Floyd?Warshall算法 25.3 用于稀疏图...
·对讨论单源最短路径的第24章做了重新组织,把对基本性质的证明移到了各自的节中。这种新的结构使我们可以更早地将注意力放在算法上。 ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路...
·对讨论单源最短路径的第24章做了重新组织,把对基本性质的证明移到了各自的节中。这种新的结构使我们可以更早地将注意力放在算法上。 ·第34.5节给出了对NP完全问题的一个有所扩展的综述,并新增了对哈密顿回路...
| 最少找硬币问题(贪心策略-深搜实现) 23 | 棋盘分割 23 | 汉诺塔 23 | STL 中的 PRIORITY_QUEUE 24 | 堆栈 24 | 区间最大频率 24 | 取第 K 个元素 25 | 归并排序求逆序数 25 | 逆序数推排列数 25 | 二分...