日志
他者的历史
|
maple 粘贴好竟然不能用，MATLAB由于计算机版本软件低无法下载，mathematic 无法执行。
package DataStructure;
import java.util.Scanner;
public class Floyd {private Graph graph;
private int[][] d;
private int[][] p;
public Floyd() {this.graph=new Graph();
d=graph.getArc();
p=new int[graph.getNumVex()][graph.getNumVex()];
initP();
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];}}}}}/**
*
*
*/public void getShortestPath(int start,int end) {StringBuilder path=new StringBuilder();
int index=start;//起始点 path.append(start+" \[RightArrow] ");
while (index!=end) {
//循环取出路径上的各个顶点 index=p[index][end];
if (index!=end) {path.append(index+" \[RightArrow]");}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("请输入定点的数目:6");
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("顶点数为：6"+this.numVex);
System.out.print("请输入边数:8");
scanner=new Scanner(System.in);
this.numEdge=scanner.nextInt();
System.out.println("边数为：8"+this.numEdge);
System.out.println("请输入（Vi，Vj）上下标i 和 j，以及权重，用逗号隔开""0,1,2"*"0,2,2"*"3,0,2"*"5,0,1"*"2,1,2"*"3,2,2"*"4,3,1"*"4,5,1");
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);}
