最短路径算法也是常用的图算法，在网上看到了一份c的代码，写的很清楚，今天有空给写成java的了，就当练手了。另，算法导论362页详细介绍了Bellman-Ford算法，本来打算再写个Dijsktra算法的，可是今天比较赖，就写这一个算法吧。
package path;
import java.util.HashSet;
public class BellmanFord {
private int MAX = Integer.MAX_VALUE;
private int N = 1024;
//顶点数 ， 边数 ， 起点
private int nodenum, edgenum, original;
//图的边
private Edge [] edge = new Edge[N];
//保存距离
private double [] dis = new double[N];
private int [] pre = new int[N];
/**
* @function
* @return
*/
boolean calculate()
{
for(int i = 1; i <= nodenum; ++i) //初始化
dis[i] = (i == original ? 0 : MAX);
for(int i = 1; i <= nodenum - 1; ++i)
for(int j = 1; j <= edgenum; ++j)
//松弛
if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost){
dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
pre[edge[j].v] = edge[j].u;
}
boolean flag = true;
//判断是否含有负权回路
for(int i = 1; i <= edgenum; ++i)
if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost){
flag = false;
break;
}
return flag;
}
void print_path(int root) //打印最短路的路径（反向）
{
while(root != pre[root]){ //前驱
System.out.print(root + "-->");
root = pre[root];
}
if(root == pre[root])
System.out.print(root + "
");
}
public boolean init(Edge [] edges){
try{
nodenum = edgenum = 0;
HashSet<Integer> vSet = new HashSet<Integer>();
for(int i = 1 ; i < edges.length ; ++i){
edgenum++;
edge[i] = edges[i];
vSet.add(edges[i].u);
vSet.add(edges[i].v);
}
nodenum = vSet.size();
return true;
}catch(Exception e){
e.printStackTrace();
return false;
}
}
private void calcShortestPath(int original){
this.original = original;
pre[original] = original;
if(calculate())
for(int i = 1; i <= nodenum; ++i){ //每个点最短路
System.out.print(dis[i] + "
");
System.out.print("Path:");
print_path(i);
}
else
System.out.println("have negative circle
");
}
public static void main(String [] args)
{
BellmanFord bellman = new BellmanFord();
Edge [] edges = new Edge [7];
edges[1] = new Edge(1 , 2 , 2);
edges[2] = new Edge(1 , 3 , 5);
edges[3] = new Edge(4 , 1 , 10);
edges[4] = new Edge(2 , 4 , 4);
edges[5] = new Edge(4 , 2 , 4);
edges[6] = new Edge(3 , 4 , 2);
bellman.init(edges);
bellman.calcShortestPath(1);
}
}
class Edge //边
{ // u为边的前驱结点，v为后继结点（暂且用前驱、后继来说）
int u, v;
//边的权重
double cost;
public Edge(int u , int v , double cost){
this.u = u;
this.v = v;
this.cost = cost;
}
}