最短路径SPF问题解决方案
-
深度优先遍历DFS
/** * 深度优先遍历Depth-First Transverse * * @param cur * @param dis * @param n * @param dest * @param edges * @param visited */ public static void dfs(int cur, int dis, int n, int dest, int[][] edges, int[] visited) { // 如果当前的dis（当前已经走过的路程）已经大于min，则没有必要再走下去 if (dis > min) { return; } // 判断是否到达了目标城市 if (cur == dest) { if (dis < min) { min = dis; } return; } // 从0号城市到n-1号城市逐个尝试 for (int j = 0; j < n; j++) { if (visited[j] == 0 && edges[cur][j] != Integer.MAX_VALUE) { visited[j] = 1; dfs(j, dis + edges[cur][j], n, dest, edges, visited); visited[j] = 0; } } } -
广度优先遍历BFS
static class Note { int x; // 城市编号 int s; // 记录从源点到其他城市的距离 public Note() { } public Note(int x, int s) { this.x = x; this.s = s; } public int getX() { return x; } public void setX(int x) { this.x = x; } public int getS() { return s; } public void setS(int s) { this.s = s; } } /** * 广度优先遍历Breath-First Transverse * * @param n * @param visited * @param edges * @param start 源点 * @param end 目标点 */ public static void bfs(int n, int[] visited, int[][] edges, int start, int end) { Note[] que = new Note[n]; // 队列的初始化 for (int i = 0; i < n; i ++) { que[i] = new Note(); } int head = 0; int tail = 0; // 从start号城市出发，将start号城市加入队列 que[tail].setX(start); que[tail].setS(0); tail++; visited[start] = 1; // 当队列不为空的时候循环 while (head < tail) { int cur = que[head].getX(); for (int j = 0; j < n; j++) { // 判断当前城市cur到目标城市j是否可达 if (edges[cur][j] != Integer.MAX_VALUE && visited[j] == 0) { // que[tail] = new Note(j, que[head].s + edges[cur][j]); que[tail].setX(j); que[tail].setS(que[head].getS() + edges[cur][j]); tail++; visited[j] = 1; } // 如果到达目标城市，更新最短路径 if (que[tail - 1].x == end) { if (que[tail - 1].getS() < min) { // 更新最小值 min = que[tail - 1].getS(); // 为了让访问过的目标重新能够被访问到 visited[que[tail - 1].getX()] = 0; // 为了避免数组溢出 tail--; break; } } } head++; } System.out.println(min); // 9 } -
弗洛伊德算法Floyd
/** * 核心代码 */ public void getCore() { // crossVertexes记录从顶点i到顶点j途经的最后一个顶点 for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (edges[i][j] < INF) { crossVertexes[i][j] = j; } else { crossVertexes[i][j] = -1; } } } // for (int i = 0; i < 4; i++) { // for (int j = 0; j < 4; j++) { // System.out.print(crossVertexes[i][j] + " "); // } // System.out.println(); // } // 从顶点i到顶点j途经顶点k的最短路径 for (int k = 0; k < size; k++) { for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (edges[i][k] < INF && edges[k][j] < INF && edges[i][j] > edges[i][k] + edges[k][j]) { edges[i][j] = edges[i][k] + edges[k][j]; // 关键代码（容易出错的地方） crossVertexes[i][j] = crossVertexes[i][k]; } } } // System.out.println("-----------------"); // for (int i = 0; i < 4; i ++) { // for (int j = 0; j < 4; j ++) { // System.out.print(edges[i][j] + " "); // } // System.out.println(); // } System.out.println("-----------------"); for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { System.out.print(crossVertexes[i][j] + " "); } System.out.println(); } } } -
迪杰斯特算法Dijkstra
public static void getCore(int n, int v0) { // dis数组保存0到其余各个顶点的初始路程 if (n >= 0) System.arraycopy(e[v0], 0, dis, 0, n); // 表示i号顶点是否已经在P集合中 for (int i = 0; i < n; i ++) { visited[i] = 0; if (dis[i] < INF) { prev[i] = v0; } else { prev[i] = -1; } } visited[v0] = 1; // 算法核心 for (int i = 0; i < n - 1; i ++) { int min = INF; int u = 0; // 寻找剩余顶点到源点的最短路径 for (int j = 0; j < n; j ++) { if (visited[j] == 0 && dis[j] < min) { min = dis[j]; u = j; } } visited[u] = 1; System.out.println("×××" + u); // 松弛操作 for (int k = 0; k < n; k ++) { if (e[u][k] < INF) { if (dis[k] > min + e[u][k]) { dis[k] = min + e[u][k]; prev[k] = u; } } } } }