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

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

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

--sunfruit

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 阅读(1655) 评论(0)  编辑  收藏 所属分类: 数据结构

 只有注册用户登录后才能发表评论。 网站导航: 相关文章: