sunfruit[请访问http://www.fruitres.cn]

--我相信JAVA能走得更远 QQ:316228067

[原创]图论应用--最短路径

    --sunfruit

求上图1点到其他各点的最短路径,依据图论知识建立矩阵模型,进一步得到代码如下

public class ShortPathA {

  private static int[][]
      a = {
      {0, 50, 10, 100000, 45, 100000}, {100000, 0, 15, 100000, 10, 100000}, {20, 100000, 0, 15, 100000, 100000}, {
      100000, 20, 100000, 0, 35, 100000}, {100000, 100000, 1000000, 30, 0, 100000}, {100000, 100000, 100000, 3, 100000, 0}
  };

  private static boolean[] mark = new boolean[a.length];
  public ShortPathA() {
    int Vo = 0; //源点
    //源点到其他各点的距离
    int[] b = new int[a.length];
    DynArrayInt S = new DynArrayInt();
    for (int i = 0; i < a.length; i++) {
      mark[i] = false;
      //b[i] = a[Vo][i];
    }
    int best = -1;
    mark[0] = true;
    b[0] = 0; //{0为源点}
    while (best != 0) {
      best = 0;
      int best_j = 0;
      for (int i = 0; i < b.length; i++)
      {
        if (mark[i]) //{对每一个已计算出最短路径的点}
        {
          for (int j = 0; j < b.length; j++) {
            if ( (!mark[j]) && (a[i][j] > 0)) {
              if ( (best == 0) || (b[i] + a[i][j] < best)) {
                best = b[i] + a[i][j];
                best_j = j;
              }
            }
          }
        }
      }
      if (best > 0) {
        b[best_j] = best;
        mark[best_j] = true;
      }

    }
    System.out.println(java.util.Arrays.toString(b));
  }

  public static void main(String[] args) {
    ShortPathA shortpath = new ShortPathA();
  }

}

posted on 2006-10-23 21:17 sunfruit 阅读(1593) 评论(0)  编辑  收藏 所属分类: 数据结构


只有注册用户登录后才能发表评论。


网站导航: