本文主要是介绍贪心算法-4.5单源最短路径之Dijkstra算法（松弛操作），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：对下图中的有向图，应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下页的表中。
问题分析：
public class test4_5 {public static void Dijkstra(int v,float[][] a,float[] dist,int[] prev){int n = dist.length;if(v<0||v>n-1) return;boolean[] s = new boolean[n];//1.初始化 dist[i]、s[i]和prev[i]for(int i=0;i<n;i++){dist[i] = a[v][i];s[i] = false;if(dist[i]==Float.MAX_VALUE) prev[i] = -1;else prev[i] = v;}s[v] = true; dist[v] = 0;for(int i=0;i<n-1;i++){ //加进去n-1个点//2.找最小——找没加进去点连接的最小权值float temp = Float.MAX_VALUE;int u = v;for(int j=0;j<n;j++){if((!s[j])&&temp>dist[j]){ //没加进去的点&&temp>dist[j]temp = dist[j];u = j;}}s[u] = true; //把点加进去//3.调整for(int j=0;j<n;j++){if((!s[j])&&dist[j]>a[u][j]+dist[u]){dist[j] = a[u][j]+dist[u];prev[j] = u;}}}}public static void main(String[] args) {int v = 0; //选定的源点为第"0"点int n = 5; //点的个数float t = Float.MAX_VALUE;float[][] a = {{t,10, t,30,100}, //邻接矩阵,表示边<i,j>的权值{t, t,50, t, t},{t, t, t, t, 10},{t, t,20, t, 60},{t, t, t, t, t}};float[] dist = new float[n];int[] prev = new int[n];Dijkstra(v,a,dist,prev);for(int i=0;i<n;i++){if(v!=i){System.out.print("从"+v+"点到"+i+"点所花的最短路长为："+dist[i]+"; 路径是："+i);int k = i;while(prev[k]!=-1){System.out.print("——"+prev[k]);k = prev[k];}}System.out.println();}}
}运行结果：
从0点到1点所花的最短路长为：10.0; 路径是：1——0
从0点到2点所花的最短路长为：50.0; 路径是：2——3——0
从0点到3点所花的最短路长为：30.0; 路径是：3——0
从0点到4点所花的最短路长为：60.0; 路径是：4——2——3——0时间复杂度：O(n^2)。
这篇关于贪心算法-4.5单源最短路径之Dijkstra算法（松弛操作）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
