Dijkstra算法
算法核心
- 计算单源最短路径
- 找到最短路径已经确定的顶点，从它出发更新其相邻顶点的最短距离
- 更新完毕后，不再关注“最短路径已经确定的顶点”
输入处理
int n = 4; // 顶点数int[][] edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}; // 边int[] vals = {2, 5, 4, 6, 2}; // 边的权重 与edges的边一一对应
邻接矩阵写法
计算从start顶点到end顶点的最短路径
public int dijDistByMatrix(int start, int end) {int[][] cost = new int[n + 1][n + 1]; // 邻接矩阵int[] dis = new int[n + 1]; // 保留最短距离boolean[] vis = new boolean[n + 1]; // 最短距离的访问情况Arrays.fill(dis, Integer.MAX_VALUE); // 最短距离初始化dis[start] = 0; // start表示起点// 初始化for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) {cost[i][j] = 0;}else {cost[i][j] = Integer.MAX_VALUE;}}}// 赋值for (int i = 0; i < edges.length; i++) {int u = edges[i][0];int v = edges[i][1];cost[u][v] = vals[i];cost[v][u] = vals[i];}// 计算while (true) {int v = -1;// 找到最小距离的下标for (int i = 1; i <= n; i++) {if (!vis[i] && (v == -1 || dis[i] < dis[v])) {v = i;}}// 如果都被使用过，则跳出循环if (v == -1) break;vis[v] = true; // 标记此最短距离已使用// 更新从最小距离下标出发到其他点的最短距离for (int u = 1; u <= n; u++) {if (dis[u] > dis[v] + cost[v][u]) {dis[u] = dis[v] + cost[v][u];}}}// 返回return dis[end];}
邻接表写法
class Edge {int to; // 终点int cost; // 边的权重Edge(int to, int cost) {this.to = to;this.cost = cost;}}class Pair {int min; // 当前的最短距离int idx; // 顶点的编号Pair(int min, int idx) {this.min = min;this.idx = idx;}}public int dijDistByTable(int start, int end) {ArrayList<Edge>[] G = new ArrayList[n + 1]; // 用于保留每个顶点边的情况PriorityQueue<Pair> que = new PriorityQueue<>(new Comparator<Pair>() {@Overridepublic int compare(Pair o1, Pair o2) {return o1.min - o2.min;}});int[] dis = new int[n + 1]; // 最短距离Arrays.fill(dis, Integer.MAX_VALUE);dis[start] = 0;que.add(new Pair(0, start));// 初始化 Gfor (int i = 1; i < G.length; i++) {G[i] = new ArrayList<>();}for (int i = 0; i < edges.length; i++) {int u = edges[i][0];int v = edges[i][1];G[u].add(new Edge(v, vals[i]));}// 计算while (!que.isEmpty()) {Pair p = que.poll();int v = p.idx;if (dis[v] < p.min) continue; // 如果当前p.min不是最短距离，则更新距离for (int i = 0; i < G[v].size(); i++) {Edge e = G[v].get(i);if (dis[e.to] > dis[v] + e.cost) {dis[e.to] = dis[v] + e.cost;que.add(new Pair(dis[e.to], e.to));}}}// 返回return dis[end];}