javaアルゴリズム導論のFlooydWarshallアルゴリズムはコードを実現します.

要約:アルゴリズム導論のFloydWarshallアルゴリズム
つの図の中で任意の2点の間の最短のパスを求めます.  

    FloydWarshall                        

                 ，      V （   ）BellmanFord  。           EV^2
              ，    V^3
                ，           V^4，        ，  FloydWarshall          
        ，            。

インスタンスコード:

package org.loda.graph;

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

import org.loda.util.In;

/**
 * 
 * @ClassName: FloydWarshall
 * @Description:                 
 * 
 *        FloydWarshall                       
 * 
 *                 ，      V （   ）BellmanFord  。           EV^2
 *              ，    V^3
 *                ，           V^4，        ，  FloydWarshall          
 *        ，            。 
 *         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];

 //             ，              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     
 * @return void     
 * @throws
 */
 public void findShortestPath() {
 //      
 for (int k = 0; k < v; k++) {
  //   k    i->j         
  for (int i = 0; i < v; i++) {
  for (int j = 0; j < v; j++) {
   //               k，          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();
  }
 }

 //            ，      i->i   d[i][i]，      0 ，    i->i              ，          
 //             ，             ，                    ，       d[0][0]，      d[i][i]
 for(int i=0;ib       
 * @param @param a
 * @param @param b
 * @param @return     
 * @return double     
 * @throws
 */
 public double distTo(int a, int b) {
 if (hasNegativeCycle())
  throw new RuntimeException("     ，       ");
 return d[a][b];
 }
 
 /**
 * 
 * @Title: printShortestPath
 * @Description:   a->b    
 * @param @return     
 * @return Iterable     
 * @throws
 */
 public boolean printShortestPath(int a,int b){
 if (hasNegativeCycle()){
  System.out.print("     ，       ");
 }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     
 * @return void     
 * @throws
 */
 public void addEdge(int a, int b, double w) {
 d[a][b] = w;
 }

 public static void main(String[] args) {
 //            
 String text1 = "F:\\  \\attach\\tinyEWDn.txt";
 //            
 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();
 }
 }

}

負の重みのループ図を採用すると、異常を投げ、負のループを提示し、最短のパスがないことを表します.
負のループを含まない図を採用すると、次のような内容が印刷されます(現在はs=0でテストしています.他の点を原点とする最短ルートは自分で試してもいいです).

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

読んでくれてありがとうございます.みなさんのご協力をお願いします.ありがとうございます.