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-Warshall算法，通常简称为Floyd算法，是一种用于解决所有对之间最短路径问题的有效算法。由Robert W...
Floyd算法的基本思想是通过动态规划逐步完善最短路径信息，通过迭代所有可能的中间节点来更新路径长度。其核心代码通常涉及一个二维数组，用于存储节点间路径的当前最短距离。 具体实现步骤如下： 1. 初始化：首先...
总结来说，Floyd算法是一种高效、灵活的求解多源最短路径问题的方法，通过动态规划逐步完善最短路径信息，具有广泛的实用价值。理解和掌握这一算法，对于从事图论、数据结构、网络优化等领域的工作有着重要意义。
Floyd算法的核心思想是通过逐步考虑所有可能的中间节点来寻找最短路径。初始时，算法假设每个节点到自身的距离为0，直接相邻节点之间的距离为边的权重。然后，对于每一对节点i和j，算法会尝试通过所有的中间节点k来...
实验选取两种经典算法——Dijkstra算法与Floyd算法，分别针对特定场景求解最短路径问题。通过本实验，学生能够： 1. 掌握最短路径的基础理论知识。 2. 熟悉Dijkstra算法与Floyd算法的工作原理及其适用场景。 3. 能够...
Floyd-Warshall算法，通常简称为Floyd算法，是一种在图中寻找所有顶点对之间最短路径的有效算法。由Robert W. Floyd于1962年提出，该算法的核心思想是通过动态规划逐步增加中间节点，以检查是否存在更短的路径。在...
3. Floyd-Warshall算法：Floyd-Warshall算法是一种解决所有对最短路径的全局算法，适合于计算稠密图中的最短路径。它通过填充一个距离矩阵，逐步考虑所有可能的中间节点，最终得到所有节点对之间的最短路径。时间...
本主题聚焦于利用Matlab来实现图论（Graph Theory）中的算法，特别是解决最短路径问题。在国赛级别的竞争中，这样的技巧能帮助团队高效地解决问题并获得高分。 图论是数学的一个分支，主要研究由点和线构成的图形...
这个报告详细介绍了如何构建一个数据结构来存储图，以及如何通过Floyd算法计算最短路径并确定最小偏心度。 1. **问题描述** - 问题设定了一个现实世界的情景，即有n个村庄，需要选择一个地点建立医院，以使其他...
Floyd算法，也称为Floyd-Warshall算法，是一种用于解决所有对之间的最短路径问题的有效方法。这个算法的核心思想是动态规划，它通过逐步增加中间节点来探索可能的最短路径。 Floyd算法的基本步骤如下： 1. 初始化...
floyd算法是求解最短路径的一种经典算法，本文分析了它求解最短路径的具体实现方法和效率，希望对大家对floyd算法有所了解。
【标题】"最短路径算法--vb源码"所涉及的知识点主要集中在计算机...通过分析这个VB源码，不仅可以学习最短路径算法的实现，还可以深入理解VB编程和软件开发的基本流程，对于提升编程技能和理解算法应用具有重要意义。
Floyd-Warshall算法通过逐步更新所有节点对之间的最短路径，最终得到完整的最短路径矩阵。C#实现时，可以创建一个二维数组来存储距离矩阵，并进行三层循环更新。 3. **Bellman-Ford算法**：与Dijkstra算法不同，...
本文将详细探讨两种著名的解决最短路径问题的算法：Dijkstra算法和Floyd算法。 **Dijkstra算法** Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出的，它主要用于寻找带权重的无环图中从单一源点到...
2. **Floyd-Warshall算法**：由罗伯特·弗洛伊德和艾伦·沃什尔提出，是一种解决所有对之间最短路径问题的动态规划算法。对于带负权边的图，此算法并不适用，但能处理所有非负边权的情况。 3. **Bellman-Ford算法**...
Java实现的Dijkstra最短路径算法是图论中的一个经典算法，用于寻找图中两个节点间的最短路径。这个算法由荷兰计算机科学家艾兹格·迪科斯彻于1956年提出，广泛应用于路由选择、网络规划、任务调度等领域。在Java编程...
Floyd算法的基本思想是通过逐步考虑所有可能的中间节点来更新最短路径信息。 在图的表示上，通常使用邻接矩阵或邻接表。对于C#程序来说，可能会使用二维数组来存储邻接矩阵，每个元素表示图中一对顶点之间是否存在...
常见的最短路径算法有Dijkstra算法、Floyd-Warshall算法、Bellman-Ford算法等。在这个程序中，可能采用了其中一种或结合多种算法来解决经过指定节点的问题。 2. **Dijkstra算法**：Dijkstra算法是最常用的单源最短...
Floyd算法广泛应用于交通网络、社交网络分析、图形处理等领域，找出两点之间最短路径，或者计算所有顶点对的最短路径。由于其全路径探索的特性，对于稠密图（边多于顶点数量的平方）效率较高，但在稀疏图（边少于...
总的来说，Floyd算法是一个强大且实用的工具，尤其在处理大量节点和边的图时，能有效地找出所有节点对之间的最短路径。通过学习和实践"RoadRearch"中的代码实例，读者可以加深对这一算法的理解，并将其应用于实际...