求教：关于无向图的Bellman-Ford算法
我用java实现bellman-ford算法，但书里面的例子关于bellman-ford的算法只用于向图。然而我的作业里面却给了一个无向图。一下是读取的文本，第一行是总顶点数，第二行是源点 source, 接下来是图的邻接矩阵表达式。
10
0
0 12 0 17 0 7 0 12 0 -7
12 0 0 -4 3 19 0 0 10 15
0 0 0 3 2 2 0 -3 20 0
17 -4 3 0 0 0 13 0 0 0
0 3 2 0 0 9 0 12 0 12
7 19 2 0 9 0 0 4 0 15
0 0 0 13 0 0 0 18 14 16
12 0 -3 0 12 4 18 0 18 0
0 10 20 0 0 0 14 18 0 0
-7 15 0 0 12 15 16 0 0 0
我运行出来似乎有错，请哪位大高手帮我看看我的代码哪里出错了。
源点为0, 总共10个顶点。
程序代码：
import *;
import java.util.*;
public class BellmanFord {
LinkedList<Edge> edges;
int distances[];
//int path[];
int numberOfVertices;
int edge;
int source;
final static int INFINITY=999;
private static class Edge {
int u,v,w;
public Edge(int u, int v, int w) {
this.u=u;
this.v=v;
this.w=w;
}
}
BellmanFord () throws IOException {
InputResult BellmanFordInput = readInput("BellmanFordinput.txt");
source = BellmanFordInput.sourceVertex;
numberOfVertices = BellmanFordInput.numberOfVertice;
int[][] inputGraph = BellmanFordInput.adjacencyMatrix;
edges = new LinkedList<Edge>();
for(int i=0; i<numberOfVertices; i++) {
for(int j =0; j< numberOfVertices; j++) {
if(inputGraph[i][j] != 0)
edges.add(new Edge(i, j, inputGraph[i][j]));
}
}
edge = edges.size();
distances = new int[numberOfVertices];
}
void relax() { //the relax operation
int i, j;
for(i=0;i<numberOfVertices;++i) {
distances[i]=INFINITY;
}
distances[source] = 0;
for (i = 0; i < numberOfVertices - 1; ++i) {
for (j = 0; j < edge; ++j) { //calculate the shortest path
if (distances[edges.get(j).u] + edges.get(j).w < distances[edges.get(j).v]) {
distances[edges.get(j).v] = distances[edges.get(j).u] + edges.get(j).w;
}
}
}
}
boolean NoCycle() {
int j;
for (j = 0; j < edge; ++j)
if (distances[edges.get(j).u] + edges.get(j).w < distances[edges.get(j).v])
return false;
return true;
}
/* The following method is going read the BellmanFordinput.txt as input and returns an object that contains
1) total number of vertices, 2) source vertex and 3) the adjacency matrix */
private static InputResult readInput(String txtfile) throws IOException{
String pathname=txtfile;
File filename=new File(pathname);
InputStreamReader reader = new InputStreamReader( new FileInputStream(filename));
BufferedReader br = new BufferedReader(reader);
StringBuffer buffer = new StringBuffer();
String line = br.readLine();
while(line!=null){
buffer.append(" "+line);
line = br.readLine();
}
String temp[]=buffer.toString().replaceFirst(" ", "").split("\\s+");
InputResult inputResult= new InputResult();
inputResult.numberOfVertice=Integer.parseInt(temp[0]);
inputResult.sourceVertex=Integer.parseInt(temp[1]);
inputResult.adjacencyMatrix=new int[inputResult.numberOfVertice][inputResult.numberOfVertice];
for(int i=0; i<inputResult.numberOfVertice; i++) { //line
for(int j=0; j<inputResult.numberOfVertice; j++){ //column
inputResult.adjacencyMatrix[ i ] [ j ] = Integer.parseInt(temp[j+10*i+2]);
}
}
return inputResult;
}
//This inner auxiliary class is for storing the BellmanFordinput.txt input result
private static class InputResult{
int numberOfVertice;
int sourceVertex;
int[][] adjacencyMatrix;
}
public static void main(String args[]) throws IOException {
BellmanFord bellmanFord = new BellmanFord ();
bellmanFord.relax();
if(bellmanFord.NoCycle()) {
System.out.println("Start from the source vertex: " + bellmanFord.source + " to " + "destination vertex: i");
for(int i=0;i<bellmanFord.numberOfVertices;i++)
if(bellmanFord.distances[i]!=INFINITY){
System.out.println(bellmanFord.source+" ==> "+ i +", shortest distance: " +bellmanFord.distances[i]);
}
else
System.out.println(bellmanFord.source+" ==> "+ i +", shortest distance: INIFINITY" );
}
else {
System.out.println(" There is a negative edge cycle ");
}
}
}
[ 本帖最后由 UAPOPPING 于 2015-6-5 10:58 编辑 ]
