suanfa.rar_最短路径 Java

package src.suanfa; import java.util.PriorityQueue; import java.util.Scanner; public class ShortestPath { /**有n个节点*/ private int n; /**节点矩阵*/ private double matrix[][] = null; /**存储单源最短路径*/ private double minpath[]; public ShortestPath(int n) { this.n = n; matrix = new double[n+1][n+1]; minpath = new double[n+1]; for(int i=1;i<=n;i++) { minpath[i] = Double.MAX_VALUE; } //初始化图 getGraphMatrix(); } /** * 构造图的矩阵(带权有向图) */ public void getGraphMatrix() { //初始化为不能连通 for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { matrix[i][j] = Double.MAX_VALUE; } } System.out.println("有多少条边？"); Scanner scan = new Scanner(System.in); int m = scan.nextInt(); System.out.println("依次输入两个顶点号(1~"+n+")和边长:例如 1 2 3"); for(int i=0;i<m;i++) { int a,b; double d; a = scan.nextInt(); b = scan.nextInt(); d = scan.nextDouble(); if(a<1 || b<1) { i--; System.out.println("顶点号不能小于1"); continue; } if(a>n||b>n) { i--; System.out.println("顶点号不能大于"+n); continue; } matrix[a][b] = d; } } /** *@param 求以第i个节点为起点的单源最短路径 */ public void shortpath(int i) { minpath[i] = 0; double curlen = 0; PriorityQueue<Node> heap = new PriorityQueue(); Node cur = new Node(i,0); heap.add(cur); while(!heap.isEmpty()) { for(int j=1;j<=n;j++) { if(matrix[cur.i][j]<Double.MAX_VALUE && cur.len+matrix[cur.i][j]<minpath[j]) { minpath[j] = cur.len+matrix[cur.i][j]; heap.add(new Node(j,minpath[j])); } } cur = heap.poll(); } //打印最短路径结果 for(int j=1;j<=n;j++) { if(minpath[j]<Double.MAX_VALUE && j!=i) { System.out.println("最短路径："); System.out.println(i+"到"+j+":"+minpath[j]); } } } public static void main(String args []) { ShortestPath s = new ShortestPath(6); s.shortpath(6); } } /** * 定义拥有自然顺序（Comparable）的节点用于优先队列 * @author 李赫元 */ class Node implements Comparable<Node> { int i; double len; public Node(int i,double l) { this.i = i; len = l; } public int compareTo(Node o) { double dif = len-o.len; if(dif>0) { return 1; } else if(dif==0) { return 0; } else { return -1; } } }