1、狄克斯特拉(Dijkstra)算法
采用狄克斯特拉(Dijkstra)算法可以求带权图(所有权值为正数)中一个顶点到其余各顶点的最短路径,称其为单源最短路径算法。
2、设计思想
用visit数组标记已访问过的元素,visit【j】=1,表示已访问过。dist【j】用来保存从源点v到顶点j的当前最短路径长度,他的初值为v的邻接点的权值。path【j】用于保存从源点v到j的最短路径长度,实际上,path【j】保存从源点v到顶点j的当前最短路径中顶点j的前一个顶点的编号,他的初值为源点(有边时)v的编号或-1(无边时)。
以下代码仅供参考
以下代码仅供参考
以下代码仅供参考
/** *作者:魏宝航 *2020年11月23日,下午19:19 */ import org.omg.CORBA.INTERNAL; import java.io.IOException; import java.util.Scanner; public class MatrixUDG { private char[] mVexs; private int[][] mMatrix; private int num; public MatrixUDG(char[] vexs, char[][] edges) { num = vexs.length; mVexs = new char[num]; for (int i = 0; i < mVexs.length; i++) mVexs[i] = vexs[i]; mMatrix = new int[num][num]; for(int i=0;i<num;i++){ for(int j=0;j<num;j++){ if(edges[i][j]=='∞'){ mMatrix[i][j]=Integer.MAX_VALUE; }else{ mMatrix[i][j]=Integer.parseInt(edges[i][j]+""); } } } } public void print() { System.out.printf("Martix Graph:\n"); for (int i = 0; i < mVexs.length; i++) { for (int j = 0; j < mVexs.length; j++){ if(mMatrix[i][j]<Integer.MAX_VALUE){ System.out.printf("%d ", mMatrix[i][j]); }else{ System.out.print("∞ "); } } System.out.printf("\n"); } } public void Dijkstra(int v){ int[] dist=new int[1000]; int[] path=new int[1000]; int[] visit=new int[1000]; int min=Integer.MAX_VALUE; int k=0; for(int i=0;i<this.num;i++){ dist[i]=this.mMatrix[v][i]; visit[i]=0; if(this.mMatrix[v][i]<Integer.MAX_VALUE){ path[i]=v; } else{ path[i]=-1; } } visit[v]=1; for(int i=0;i<this.num;i++){ min=Integer.MAX_VALUE; for(int j=0;j<this.num;j++){ if(visit[j]==0&&dist[j]<min){ min=dist[j]; k=j; } } visit[k]=1; for(int j=0;j<this.num;j++){ if(visit[j]==0){ if(this.mMatrix[i][j]<Integer.MAX_VALUE&&dist[k]+this.mMatrix[k][j]<dist[j]){ dist[j]=dist[k]+this.mMatrix[k][j]; path[j]=k; } } } } } public static void main(String[] args) { char[] vexs={'0','1','2','3','4','5'}; char[][] edges=new char[][]{ {'0','6','1','5','∞','∞'}, {'6','0','5','∞','3','∞'}, {'1','5','0','5','6','4'}, {'5','∞','5','0','∞','2'}, {'∞','3','6','∞','0','6'}, {'∞','∞','4','2','6','0'}, }; MatrixUDG g=new MatrixUDG(vexs,edges); g.print(); } }