Dijkstra算法解决单源最短路径问题实例

Dijkstra算法解决单源最短路径问题实例

1、实例题

用Dijkstra算法解决单源最短路径问题，并给出算法的时间复杂性分析。用你写的程序求出下图节点1到任何一个节点的最短路径，包括最短路径值及其最短路径。

2、Java实现

代码部署结构图

main函数：

package com;import com.dynamicProgramming.*;public class Main
{public static void main(String[] args) {//输入图的路径信息  -1代表无法直达  0代表自身  正整数代表路径长度int[][] weight= {{0,9,7,3,2,-1,-1,-1,-1,-1,-1,-1},{9,0,-1,-1,-1,4,2,1,-1,-1,-1,-1},{7,-1,0,-1,-1,2,7,-1,-1,-1,-1,-1},{3,-1,-1,0,-1,-1,-1,11,-1,-1,-1,-1},{2,-1,-1,-1,0,-1,11,8,-1,-1,-1,-1},{-1,4,2,-1,-1,0,-1,-1,6,5,-1,-1},{-1,2,7,-1,11,-1,0,-1,4,3,-1,-1},{-1,1,-1,11,8,-1,-1,0,-1,5,6,-1},{-1,-1,-1,-1,-1,6,4,-1,0,-1,-1,4},{-1,-1,-1,-1,-1,5,3,5,-1,0,-1,2},{-1,-1,-1,-1,-1,-1,-1,6,-1,-1,0,5},{-1,-1,-1,-1,-1,-1,-1,-1,4,2,5,0},};String[] str= {"1","2","3","4","5","6","7","8","9","10","11","12"};int len=str.length;Dijkstra dijkstra=new Dijkstra(len);//依次选择作为源点，并调用dijkstra函数计算最短路径for(int i=0;i<str.length;i++){dijkstra.dijkstra(weight, str, i);System.out.println();}}
}

Dijkstra类：

package com.dynamicProgramming;import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;public class Dijkstra
{private Queue visited;private int[] distance;public Dijkstra(int len) {// TODO Auto-generated constructor stubvisited=new LinkedList();distance=new int[len];}private int getIndex(Queue q,int[] dis){int k=-1;int min_num=Integer.MAX_VALUE;for(int i=0;i<dis.length;i++){if(!q.contains(i)){if(dis[i]<min_num){min_num=dis[i];k=i;}}}return k;}public void dijkstra(int[][] weight,Object[] str,int v){HashMap path;path=new HashMap();for(int i=0;i<str.length;i++)path.put(i, "");//初始化路径长度数组distancefor(int i=0;i<str.length;i++){path.put(i, (i)+""+str[v]);if(i==v)distance[i]=0;else if(weight[v][i]!=-1){distance[i]=weight[v][i];path.put(i, (i)+"-->"+str[i]);}elsedistance[i]=Integer.MAX_VALUE;}visited.add(v);while(visited.size()<str.length){int k=getIndex(visited,distance);//获取未访问点中距离源点最近的点visited.add(k);if(k!=-1){for(int j=0;j<str.length;j++){if(weight[k][j]!=-1)//判断k点能够直接到达的点{//通过遍历各点，比较是否有比当前更短的路径，有的话，则更新distance，并更新path。if(distance[j]>distance[k]+weight[k][j]){distance[j]=distance[k]+weight[k][j];path.put(j, (k)+"-->"+str[j]);}}}}}for(int h=0;h<str.length;h++){System.out.printf(str[v]+"-->"+str[h]+":"+distance[h]+" ");if(distance[h]==Integer.MAX_VALUE)System.out.print(str[v]+"-->"+str[h]+"之间没有可通行路径");elseSystem.out.print(str[v]+"-"+str[h]+"之间有最短路径，具体路径为："&#(h).toString());System.out.println();}visited.clear();}}

Graph类：

package com.dynamicProgramming;public class Graph
{final int max=100;//顶点节点public class VexNode{int adjvex;int data;}VexNode[] vexNodes;int[] thevexs; //顶点集合int[][] edges = new int[max][max]; //边集合/** 创建图*/public void createGraph(Graph graph,int[][] A,int[] vexs) {thevexs=vexs;for (int i = 0; i < vexs.length; i++) {for (int j = 0; j < vexs.length; j++) {graph.edges[i][j] = A[i][j];}}}/** 输出图*/public void printGraph(Graph graph) {for (int i = 0; i < graph.thevexs.length; i++) {for (int j = 0; j < graph.thevexs.length; j++) {//没有路径则输出/if (graph.edges[i][j]==1000) {System.out.printf("%4s","/");}else {System.out.printf("%4d",graph.edges[i][j]);}}System.out.println("n");}}
}