java算法導(dǎo)論之FloydWarshall算法實(shí)現(xiàn)代碼

更新時(shí)間：2017年05月17日 11:59:42 作者：jonathan_loda

這篇文章主要介紹了算法導(dǎo)論之FloydWarshall算法實(shí)現(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下

摘要: 算法導(dǎo)論之FloydWarshall算法

求一個(gè)圖中任意兩點(diǎn)之間的最短路徑

    FloydWarshall算法是通過動(dòng)態(tài)規(guī)劃來計(jì)算任意兩點(diǎn)之間的最短路徑 

        如果普通求最短路徑，可以對(duì)圖進(jìn)行V次（頂點(diǎn)數(shù)）BellmanFord算法。 這樣的話時(shí)間復(fù)雜度為EV^2
        如果是稀疏圖，則近似于V^3
        但是如果是密集圖，則時(shí)間復(fù)雜度會(huì)近似達(dá)到V^4，這種情況需要優(yōu)化，這里FloydWarshall通過動(dòng)態(tài)規(guī)劃進(jìn)行優(yōu)化
        ，并且使用鄰接矩陣來表示圖。

實(shí)例代碼：

package org.loda.graph;

import java.math.BigDecimal;
import java.math.RoundingMode;

import org.loda.util.In;

/**
 * 
 * @ClassName: FloydWarshall
 * @Description: 求一個(gè)圖中任意兩點(diǎn)之間的最短路徑
 * 
 *        FloydWarshall算法是通過動(dòng)態(tài)規(guī)劃來計(jì)算任意兩點(diǎn)之間的最短路徑
 * 
 *        如果普通求最短路徑，可以對(duì)圖進(jìn)行V次（頂點(diǎn)數(shù)）BellmanFord算法。 這樣的話時(shí)間復(fù)雜度為EV^2
 *        如果是稀疏圖，則近似于V^3
 *        但是如果是密集圖，則時(shí)間復(fù)雜度會(huì)近似達(dá)到V^4，這種情況需要優(yōu)化，這里FloydWarshall通過動(dòng)態(tài)規(guī)劃進(jìn)行優(yōu)化
 *        ，并且使用鄰接矩陣來表示圖。 
 *         d(i,j); if m=0 
 *        D(i,j,m)={
 *         min(D(i,m,m-1)+D(m,j,m-1),D(i,j,m-1)); if m!=0
 * @author minjun
 * @date 2015年6月1日 上午9:39:42
 * 
 */
public class FloydWarshall {

 private double[][] d;

 private int[][] prev;

 private int v;

 private boolean negativeCycle;

 public FloydWarshall(int v) {
 this.v = v;

 d = new double[v][v];

 prev = new int[v][v];

 // 默認(rèn)設(shè)置所有節(jié)點(diǎn)都不可達(dá)，而自己到自己是可達(dá)并且距離為0.0
 for (int i = 0; i < v; i++) {
  for (int j = 0; j < v; j++) {
  d[i][j] = Double.POSITIVE_INFINITY;
  prev[i][j] = -1;
  if(i==j){
   d[i][j] = 0;
  }
  }
 }
 }

 /**
 * 
 * @Title: findShortestPath
 * @Description: 查詢最短路徑
 * @param 設(shè)定文件
 * @return void 返回類型
 * @throws
 */
 public void findShortestPath() {
 //查找最短路徑
 for (int k = 0; k < v; k++) {
  //將每個(gè)k值考慮成i->j路徑中的一個(gè)中間點(diǎn)
  for (int i = 0; i < v; i++) {
  for (int j = 0; j < v; j++) {
   //如果存在使得權(quán)重和更小的中間值k，就更新最短路徑為經(jīng)過k的路徑
   if (d[i][j] > d[i][k] + d[k][j]) {
   d[i][j] = d[i][k] + d[k][j];
   prev[i][j]=k;
   }
  }
  }
 }

 //四舍五入距離
 for (int i = 0; i < v; i++) {
  for (int j = 0; j < v; j++) {
  d[i][j] = new BigDecimal(d[i][j]).setScale(2,
   RoundingMode.HALF_UP).doubleValue();
  }
 }

 //檢測(cè)負(fù)權(quán)重環(huán)的方式很簡(jiǎn)單，就是判斷所有i->i的距離d[i][i]，如果存在小于0的，表示這個(gè)i->i的環(huán)路的權(quán)重和形成了一個(gè)負(fù)值，也就是存在這個(gè)負(fù)權(quán)重
 //在之前的其他最短路徑算法中，無法通過這個(gè)方法來檢測(cè)負(fù)環(huán)，因?yàn)橹奥窂骄嚯x都是保存在一個(gè)一維數(shù)組中，相等于只能檢測(cè)d[0][0]，無法檢測(cè)每個(gè)d[i][i]
 for(int i=0;i<v;i++){
  if(d[i][i]<0)
  negativeCycle=true;
 }
 }

 /**
 * 
 * @Title: hasNegativeCycle
 * @Description: 是否擁有負(fù)權(quán)重環(huán)
 * @param @return 設(shè)定文件
 * @return boolean 返回類型
 * @throws
 */
 public boolean hasNegativeCycle() {
 return negativeCycle;
 }

 /**
 * 
 * @Title: distTo
 * @Description: a->b最短路徑的距離
 * @param @param a
 * @param @param b
 * @param @return 設(shè)定文件
 * @return double 返回類型
 * @throws
 */
 public double distTo(int a, int b) {
 if (hasNegativeCycle())
  throw new RuntimeException("有負(fù)權(quán)重環(huán)，不存在最短路徑");
 return d[a][b];
 }
 
 /**
 * 
 * @Title: printShortestPath
 * @Description: 打印a->b最短路徑
 * @param @return 設(shè)定文件
 * @return Iterable<Integer> 返回類型
 * @throws
 */
 public boolean printShortestPath(int a,int b){
 if (hasNegativeCycle()){
  System.out.print("有負(fù)權(quán)重環(huán)，不存在最短路徑");
 }else if(a==b)
  System.out.println(a+"->"+b);
 else{
  System.out.print(a+"->");
  path(a,b);
  System.out.print(b);
 }
 return true;
 }

 private void path(int a, int b) {
 int k=prev[a][b];
 
 if(k==-1){
  return;
 }
 
 path(a,k);
 System.out.print(k+"->");
 path(k,b);
 }
 
 

 /**
 * 
 * @Title: addEdge
 * @Description: 添加邊
 * @param @param a
 * @param @param b
 * @param @param w 設(shè)定文件
 * @return void 返回類型
 * @throws
 */
 public void addEdge(int a, int b, double w) {
 d[a][b] = w;
 }

 public static void main(String[] args) {
 // 不含負(fù)權(quán)重環(huán)的文本數(shù)據(jù)
 String text1 = "F:\\算法\\attach\\tinyEWDn.txt";
 // 含有負(fù)權(quán)重環(huán)的文本數(shù)據(jù)
 String text2 = "F:\\算法\\attach\\tinyEWDnc.txt";

 In in = new In(text1);

 int n = in.readInt();
 FloydWarshall f = new FloydWarshall(n);

 int e = in.readInt();

 for (int i = 0; i < e; i++) {
  f.addEdge(in.readInt(), in.readInt(), in.readDouble());
 }

 f.findShortestPath();

 int s = 0;
 for (int i = 0; i < n; i++) {
  System.out.println(s + "到" + i + "的距離為:" + f.distTo(s, i));
  f.printShortestPath(s, i);
  System.out.println();
 }
 }

}

如果采用負(fù)權(quán)重環(huán)圖，則會(huì)拋出異常，提示負(fù)環(huán)并表示無最短路徑

如果采用不含負(fù)環(huán)的圖，則會(huì)打印如下內(nèi)容（目前以s=0作測(cè)試，其他點(diǎn)作為原點(diǎn)的最短路徑可以自行嘗試）：

0到0的距離為:0.0
0->0

0到1的距離為:0.93
0->2->7->3->6->4->5->1
0到2的距離為:0.26
0->2
0到3的距離為:0.99
0->2->7->3
0到4的距離為:0.26
0->2->7->3->6->4
0到5的距離為:0.61
0->2->7->3->6->4->5
0到6的距離為:1.51
0->2->7->3->6
0到7的距離為:0.6
0->2->7

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持!

您可能感興趣的文章: