|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 |
import java.util.*; /** * 用堆实现了从一个点到其他点的最短路径 * @author 李赫元 */ 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; } } } |
单源最短路径之Java实现（使用Java内置优先队列）
Leave a reply