最短路径--Floyd算法代码,Java代码库,德仔网

代码语言

代码分类

【Java】最短路径--Floyd算法

作者:Kevin / 发布于2015/10/14/ 670

Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。


	package graph.dijkstra.floyd;

	
	/**
	* Created by xu on 14-3-15.
	*/

	class Node {
	 String name;
	 boolean isVisit;
	}

	public class Floyd {
	 static int LENGTH = 5;
	 static int WEIGHT = 1 << 20;

	
	 int paths[][] = new int[LENGTH][LENGTH];
	 Node nodes[] = new Node[LENGTH];

	 public void init() {
	 for (int i = 0; i < LENGTH; i++) {
	 Node node = new Node();
	 node.name = "V" + i;
	 nodes[i] = node;
	 }

	 for (int i = 0; i < LENGTH; i++) {
	 for (int j = 0; j < LENGTH; j++) {
	 if (i == j) {
	 continue;
	 }
	 paths[i][j] = WEIGHT;
	 }
	 }

	 //初始化边连线
	 paths[0][1] = 10;
	 paths[0][3] = 30;
	 paths[0][4] = 100;

	 paths[1][2] = 50;
	 paths[2][4] = 10;

	 paths[3][2] = 20;
	 paths[3][4] = 60;
	 }

	 public void calc() {

	 int minDist[][] = new int[LENGTH][LENGTH]; //0到各节点的最小距离， 无连线的距离为最大值 WEIGHT;
	 for (int i = 0; i < LENGTH; i++) {
	 for (int j = 0; j < LENGTH; j++) {
	 minDist[i][j] = paths[i][j];
	 }
	 }

	 for (int i = 0; i < LENGTH; i++) {
	 for (int j = 0; j < LENGTH; j++) {
	 for (int k = 0; k < LENGTH; k++) {
	 if (minDist[i][k] + minDist[k][j] < minDist[i][j]) {
	 minDist[i][j] = minDist[i][k] + minDist[k][j];
	 }
	 }
	 }
	 }

	
	 for (int i = 0; i < LENGTH; i++) {
	 for (int j = 0; j < LENGTH; j++) {
	 System.out.print(minDist[i][j]);
	 System.out.print(", ");
	 }

	 System.out.println("");
	 }

	 }

	 public static void main(String[] args) {
	 Floyd floyd = new Floyd();
	 floyd.init();
	 floyd.calc();
	 }
	}

试试其它关键字

　Floyd算法　

同语言下

可能有用的

Kevin贡献的其它代码(8)