QQ :375061590
用到两个重要矩阵:
1.d[numVex][numVex] (numVex图的顶点数):最开始该矩阵就是图的邻接矩阵,经过Floyd算法处理开后,d[numVex][numVex]中的d[i][j],表示着从顶点i到j的最短路径的权重。
2.p[numVex][numVex]:p[i][j]表示从i到j的最短路径上 i的后继,例如1到5最短路劲为1-2-4-5 那么p[1][5]==2 ,最开始构建的p矩阵中p[i][j]= j
算法核心思想: 三圈for循环
for (int k = 0; k < graph.getNumVex(); k++) {
for (int v = 0; v < graph.getNumVex(); v++) {
for (int w = 0; w < graph.getNumVex(); w++) {
if (d[v][w] > d[v][k] + d[k][w]) {
d[v][w] = d[v][k] + d[k][w];
p[v][w] = p[v][k];// p[v][w]是v--w最短路径上 v的下一顶点
}
}
}
}
第一层 k是作为中间顶点
第二层 v是作为起始顶点
第三层 w是作为终点顶点
内层核心代码:
以v为起点,w为终点,再以k作为v和w之间的中间点,去判断d[v][ w]和d[v][k] + d[k][w]的大小关系,如果d[v][w] > d[v][k] + d[k][w],说明找到从v→w的更短路径了,此时更改d[v][w]的值为d[v][k] + d[k][w]。
p[v][w]的值也要相应改成p[v][k]的值,因为 p[v][k]的值是v→k最短路径上v的后继顶点,而v→w这段最短路径是连接在v→k这段路径后面的,所以令所当然p[v][w]也要指向p[v][k]。
注意:最外层的k循环,前面的n此循环的结果跟后面n+1次循环的错做过程是息息相关,
三次循环完成后,各个顶点之间的最短路径权重会存储在d矩阵中:d[i][j]表示i→j的最短路径权重。
p中则存储着路径上的顶点,如果把i→j最短路径上的顶点列出来呢?
代码:
//求start→end 最短路径上的顶点
StringBuilder path = new StringBuilder();
int index = start;//起始点
path.append(start + " → ");
while (index != end) {
//循环取出路径上的各个顶点
index = p[index][end];
if(index != end){
path.append(index + " →");
}
}
用一个while循环循环 index = p[index][end];直到达到终点
假设该最短路径为 start→A→B→C→end
则执行过程是:
index = p[start][end]; →A
path== start→A →
index = p[A][end]; →B
path== start→A →B →
index = p[B][end]; →C
path== start→A →B →C→
index = p[C][end]; →end
path== start→A →B →C→end
这个就是p矩阵的妙处
测试:
图:
请输入定点的数目:5 顶点数为:5 请输入边数:7 边数为:7 请输入(Vi,Vj)上下标i 和 j,以及权重,用逗号隔开 0,1,5 0,4,7 1,2,4 4,2,8 1,3,2 2,3,6 4,3,1 初始的d矩阵 0 5 9999 9999 7 5 0 4 2 9999 9999 4 0 6 8 9999 2 6 0 1 7 9999 8 1 0 初始的p矩阵 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 处理后的d矩阵 0 5 9 7 7 5 0 4 2 3 9 4 0 6 7 7 2 6 0 1 7 3 7 1 0 处理后的p矩阵 0 1 1 1 4 0 1 2 3 3 1 1 2 3 3 1 1 2 3 4 0 3 3 3 4 求最短路径 请输入起点: 0 请输入终点: 2 从0到2的最短路径为9 该路劲为:0 → 1 →2 是否继续计算其他最短路径 Y/N? y 求最短路径 请输入起点: 0 请输入终点: 3 从0到3的最短路径为7 该路劲为:0 → 1 →3 是否继续计算其他最短路径 Y/N? y 求最短路径 请输入起点: 4 请输入终点: 1 从4到1的最短路径为3 该路劲为:4 → 3 →1 是否继续计算其他最短路径 Y/N? y 求最短路径 请输入起点: 2 请输入终点: 4 从2到4的最短路径为7 该路劲为:2 → 3 →4 是否继续计算其他最短路径 Y/N?
源代码:
package DataStructure; import java.util.Scanner; public class Floyd { private Graph graph; private int[][] d;// 用来存储顶点到顶点之间最短路径的权重 private int[][] p;// p[1][5]表示1到5的最短路径上 1的后继,例如1到5最短路劲为1-2-4-5 那么p[1][5]==2 public Floyd() { this.graph = new Graph(); d = graph.getArc(); p = new int[graph.getNumVex()][graph.getNumVex()]; initP();// 初始化矩阵p System.out.println("初始的d矩阵\n"); for (int i = 0; i < graph.getNumVex(); i++) { for (int j = 0; j < graph.getNumVex(); j++) { System.out.print(d[i][j] + " "); } System.out.println("\n"); } System.out.println("初始的p矩阵\n"); for (int i = 0; i < graph.getNumVex(); i++) { for (int j = 0; j < graph.getNumVex(); j++) { System.out.print(p[i][j] + " "); } System.out.println("\n"); } work(); System.out.println("处理后的d矩阵\n"); for (int i = 0; i < graph.getNumVex(); i++) { for (int j = 0; j < graph.getNumVex(); j++) { System.out.print(d[i][j] + " "); } System.out.println("\n"); } System.out.println("处理后的p矩阵\n"); for (int i = 0; i < graph.getNumVex(); i++) { for (int j = 0; j < graph.getNumVex(); j++) { System.out.print(p[i][j] + " "); } System.out.println("\n"); } } /** * 初始化p矩阵 * */ private void initP() { for (int i = 0; i < graph.getNumVex(); i++) { for (int j = 0; j < graph.getNumVex(); j++) { p[i][j] = j; } } } /** * 对d和p进行变化 * */ private void work() { for (int k = 0; k < graph.getNumVex(); k++) { for (int v = 0; v < graph.getNumVex(); v++) { for (int w = 0; w < graph.getNumVex(); w++) { if (d[v][w] > d[v][k] + d[k][w]) { d[v][w] = d[v][k] + d[k][w]; p[v][w] = p[v][k];// p[v][w]是v--w最短路径上 v的下一顶点 } } } } } /** * 获取最短路劲 * */ public void getShortestPath(int start, int end) { StringBuilder path = new StringBuilder(); int index = start;// 起始点 path.append(start + " → "); while (index != end) { // 循环取出路径上的各个顶点 index = p[index][end]; if (index != end) { path.append(index + " →"); }else { path.append(index); } } System.out.println("从" + (start) + "到" + (end) + "的最短路径为" + d[start][end] + "\n该路劲为:" + path.toString()); } public static void getShortestPath(Floyd floyd) { Scanner scanner = new Scanner(System.in); System.out.println("求最短路径\n请输入起点:"); int start = scanner.nextInt(); System.out.println("请输入终点:"); int end = scanner.nextInt(); floyd.getShortestPath(start, end); System.out.println("是否继续计算其他最短路径 Y/N? "); String tag = scanner.next(); if (tag.toLowerCase().equals("y")) { getShortestPath(floyd); } } /** * 图内部类 * * @author ccf * */ class Graph { /** * 定点数 * */ private int numVex = 0; private int arc[][] = null; private int numEdge = 0; private final int INFINITY = 9999; public Graph() { System.out.print("请输入定点的数目:"); Scanner scanner = new Scanner(System.in); this.numVex = scanner.nextInt(); arc = new int[numVex][numVex]; for (int i = 0; i < numVex; i++) { for (int j = 0; j < numVex; j++) { arc[i][j] = INFINITY; } } for (int i = 0; i < numVex; i++) { arc[i][i] = 0; } System.out.println("顶点数为:" + this.numVex); System.out.print("请输入边数:"); scanner = new Scanner(System.in); this.numEdge = scanner.nextInt(); System.out.println("边数为:" + this.numEdge); System.out.println("请输入(Vi,Vj)上下标i 和 j,以及权重,用逗号隔开"); for (int i = 1; i <= numEdge; i++) { scanner = new Scanner(System.in); String a = scanner.nextLine(); String[] b = a.split(","); // System.out // .println("输入了:" + Integer.parseInt(b[0]) + " " // + Integer.parseInt(b[1]) + " " // + Integer.parseInt(b[2])); arc[Integer.parseInt(b[0])][Integer.parseInt(b[1])] = Integer .parseInt(b[2]); arc[Integer.parseInt(b[1])][Integer.parseInt(b[0])] = Integer .parseInt(b[2]); } } public int[][] getArc() { return arc; } public int getNumVex() { return numVex; } } public static void main(String[] args) { Floyd floyd = new Floyd(); getShortestPath(floyd); } }
相关推荐
floyd算法是求解最短路径的一种经典算法,本文分析了它求解最短路径的具体实现方法和效率,希望对大家对floyd算法有所了解。
实现了Floyd最短路径算法,两个实例,代码中写有说明,简单易懂,非常适合初学者学习路径分析算法。
通过对Floyd算法进行深入地研究分析,提出了一种新的求取矿井中任意两点间最短路径的算法:Floyd动态优化算法。该算法通过引入插入数组、可达数组以及可发数组,使得算法在求解最短路径前自动修改能够最小化路径的节点,...
最短路径分析广泛应用于事故抢修、交通指挥、GPS导航等行业应用中。算法具体的形式包括:确定起点的最短路径问题,即已知起始结点,求最短路径的问题。用于解决最短路径问题的算法被称做"最短路径算法", 有时被简称...
算法思想:将各收费站及其...基于以上分析:车辆从任意A进站从任意B出站的收费问题就演化成求加权图中任意两点间最短路径的问题(前提:过路费按最短路径收取),采用floyd算法很容易实现求任意两点间最短路径的问题
基于MultiGen Creator/Vega...该算法不但克服了狄克斯特拉算法中结点检索冗余问题,又引入Floyd算法中的矩阵思想,对无向密集的三维巷道的路径检索非常有效,并以VC++6.0为开发平台,基于MFC技术开发实现矿井最优路径模拟。
很好的空间分析最短路径算法,可以借鉴学习的例子
一种新的保证用户QoS的最短路径算法_F_M算法,戴盛青,,针对第三代移动通信系统中,不同用户有不同的QoS要求的情况,分析Floyd算法和M算法的基本思想将二者结合起来,形成一种新的用以求解
主要使用了Dijkstra算法,Floyd算法。 主要功能有六项:1、烟台大学的平面图。2、景点的介绍。3、从一个景点到其他地方的所有最短路径。4、两景点间的最短路径。5、计算从一个地方到另一个地方所要花费的时间。6、...
主要介绍了Python基于Floyd算法求解最短路径距离问题,结合完整实例形式详细分析了Python使用Floyd算法求解最短路径距离问题的相关操作技巧与注意事项,需要的朋友可以参考下
主要介绍了C++实现多源最短路径之Floyd算法,结合实例形式分析了多源最短路径之Floyd算法的原理、实现方法及核心代码,需要的朋友可以参考下
求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。全局最短...
通过对交通调度系统信息分调需求分析,构建交互型Floyd算法模型.基于Floyd算法设计出交通调度系统 最短路径,并通过仿真设计和测试运行该程序,程序运行良好.
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
分析了时延受限的Steiner树问题,总结了在构建组播树过程中的代价和计算复杂度变化规律,并根据实际网络环境,从优化最短路径出发,提出了一种基于优化最短路径的时延受限组播路由算法AOSPMPH。该算法以 MPH算法为...
针对常见的交通道路最短路径问题, 提出标准矩形网络的概念, 分析其节点间最短路径的性质, 并在此基础上给出一种新颖的最短路径求解算法. 该算法利用标准矩形网络的几何性质, 简化了搜索方向和步长的判断, 同时指出...
java界面实现Floyd算法求解最短路径问题。算法分析实习项目,直接导入文件就可以运行。使用JPanel动态构造问题,然后程序给出结果。
利用图论中的Floyd算法求解出了各个区域之间的最短路径,得到了D矩阵和R矩阵(其中D矩阵直观的表达出任意两个区之间的最短路径,R矩阵又列出了任意两个区最短路径具体的路线),进而成功解决了如何安排有限个站点...
php-floydwarshall Floyd-Warshall算法PHP实现 如维基百科所述:“在计算机科学中,FloydWarshall算法是一种用于在加权有向图中找到最短路径的图分析算法。该算法的一次执行将在所有顶点对之间找到最短路径。”
算法专业化该资料库包含斯坦福大学...4.最后,本部分的主题是:最短路径(Bellman-Ford,Floyd-Warshall,Johnson),NP完整性及其对算法设计者的意义以及应对计算上棘手的问题的策略(启发式分析,局部搜索) 。