要求写一个Dijskstra 的计算单源最短路径， 现在已经用二项堆进行了改进，现在的问题是无法读取文件中的数值并且进行计算。希望高手指教！
以下是我写的源码：package Dijkstra;public class Edge implements Comparable<Edge> {
private Vertex u, v;
private int weight; /**
* Comparable edge class based on weight. Order of u and v does not matter.
*
* @param u
* @param v
* @param weight
*/
public Edge(Vertex u, Vertex v, int weight) {
setU(u);
setV(v);
setWeight(weight);
} @Override
public int hashCode() {
return (u == null ? 0 : u.hashCode()) ^ (v == null ? 0 : v.hashCode())^ weight;
} @Override
public boolean equals(Object o) {
if (o instanceof Edge) {
Edge e = (Edge) o;
return weight == e.weight
&& ((u.equals(e.u) && v.equals(e.v)) || (u.equals(e.v) && v
.equals(e.u)));
} else {
return false;
}
} public int compareTo(Edge e) {
return weight - e.getWeight();
} public int getWeight() {
return weight;
} public void setWeight(int weight) {
this.weight = weight;
} public Vertex getU() {
return u;
} public void setU(Vertex u) {
this.u = u;
} public Vertex getV() {
return v;
} public void setV(Vertex v) {
this.v = v;
} public String toString() {
return "{(" + u + ", " + v + "): " + weight + "}";
}
}
package Dijkstra;public class Vertex { private int id;
private String name; /**
* A simple vertex class
*
* @param id
*/
Vertex(String name){
this.name = name;
} public String getName() {
return name;
} public String toString() {
return name;
} @Override
public boolean equals(Object o) {
if (o != null && o instanceof Vertex) {
Vertex v = (Vertex) o;
return name.equals(v.name);
} else {
return false;
}
} public int hashCode() {
return name.hashCode();
}}
package Dijkstra;import java.io.*;
import java.util.*;
import java.util.Map.Entry;public class AdjacencyList { private HashMap<Vertex, Map<Vertex, Integer>> adjList;
public AdjacencyList(File file) throws IOException{
adjList = new HashMap<Vertex, Map<Vertex, Integer>>();
Scanner scanner = new Scanner(file);
while (scanner.hasNext()){
String currentLine = scanner.nextLine();
Scanner scannerIn = new Scanner(currentLine);
if (currentLine.length()>1){
Vertex vertex1 = new Vertex(scannerIn.next());
Vertex vertex2 = new Vertex(scannerIn.next());
int weight = Integer.parseInt(scannerIn.next());
if (!adjList.containsKey(vertex1)){
adjList.put(vertex1, new HashMap<Vertex,Integer>());
}
if (!adjList.containsKey(vertex2)){
adjList.put(vertex2, new HashMap<Vertex,Integer>());
}
adjList.get(vertex1).put(vertex2, weight);
adjList.get(vertex2).put(vertex1, weight);
}
}
}
public Set<Entry<Vertex,Integer>> adjVertices(Vertex last){
return adjList.get(last).entrySet();
}
public String toString() {
String result = "";
Set<Entry<Vertex,Map<Vertex,Integer>>> set = adjList.entrySet();
for (Entry<Vertex,Map<Vertex,Integer>> entry:set){
result = result+entry.getKey()+":";
Map<Vertex,Integer> map = entry.getValue();
Set<Entry<Vertex,Integer>> adjVert = map.entrySet();
for (Entry<Vertex,Integer> vEntry:adjVert){
result = result+" ("+vEntry.getKey()+", "+vEntry.getValue()+")";
}
result = result+"\n";
}
return result;
}
public Map<Vertex, Map<Vertex, Integer>> getAdjList() {
return adjList;
}}package Dijkstra;
import java.util.LinkedList;public class Path implements Comparable<Path>{
/**
* The cumulative weight of the path.
*/
private int weight; /**
* The first and last vertices of the path.
*/
private Vertex start, end; /**
* The collection of edges that represent the path.
*/
private LinkedList<Edge> edges; /**
* Create an initial path where start and end are the given vertex
*
* @param vertex
* a vertex
*/
public Path(Vertex vertex) {
start = vertex;
end = vertex;
edges = new LinkedList<Edge>();
weight = 0;
} /**
* Assume that one of the vertices (either u or v) in the edge is the end vertex of old. Copies
* the old path and adds the edge e. (Make sure to update the end vertex, and weight correctly)
*
* @param old
* a path that ends in u or v
* @param e
* an edge between vertices u and v
*/
public Path(Path old, Edge e) {
LinkedList<Edge> edges = new LinkedList<Edge>(old.edges);
edges.add(e);
this.start = edges.getFirst().getU();
this.end = e.getV();
this.edges = edges;
for (int i=0;i<this.edges.size();i++){
weight += this.edges.get(i).getWeight();
}
} /**
* The compareTo method compares the cumulative weights of two Path objects
* @return -The integer representing the comparison between the two Path objects.
*/
@Override
public int compareTo(Path that) {
int result = 0;
if (this.weight<that.weight){
result = -1;
}
else if (this.weight>that.weight){
result = 1;
}
return result;
} /**
* The equals method compares two Path objects and determines whether they are equal by weight and
* instances of the start and end vertices.
* @param path -The Path object being compared.
* @return -The boolean value describing the two objects' equality.
*/
public boolean equals(Path path){
if (path.start.equals(this.start) && path.end.equals(this.end) && path.weight==this.weight){
return true;
}
return false;
} /**
* The toString method returns the string representation of the path. *Extra Credit*
* @return -The String representation of the path in the specified format.
*/
@Override
public String toString() {
String result = "";
if (start==end){
result = "["+weight+"] ("+start+")";
}
else{
result = "["+weight+"]";
for(Edge edge:edges){
result = result+" ("+edge.getU()+", "+edge.getV()+", "+edge.getWeight()+")";
}
}
return result;
} /**
* The getWeight method acts as a getter for the weight of the path.
* @return -The integer representing the weight of the path.
*/
public int getWeight() {
return weight;
} /**
* The getStart method acts as a getter for the starting (first) vertex of the path.
* @return -The Vertex object that is first in the path.
*/
public Vertex getStart() {
return start;
} /**
* The getEnd method acts as a getter for the ending (last) vertex of the path.
* @return -The Vertex object that is last in the path.
*/
public Vertex getEnd() {
return end;
} /**
* The getEdges method acts as a getter for the collection of edges (ArrayList).
* @return -The ArrayList of edges in the path.
*/
public LinkedList<Edge> getEdges() {
return edges;
}
}
package Dijkstra;import java.io.File;
import java.io.IOException;
import java.util.PriorityQueue;
import java.util.Scanner;public class EdgeList { /**
* The Collection object that holds the 'list' of edges.
*/
private PriorityQueue<Edge> edges; /**
*
* @param txtFile -The File object that contains the information necessary to create the list of edges.
* @throws IOException
*/
public EdgeList(File txtFile) throws IOException {
edges = new PriorityQueue<Edge>();
Scanner scanner = new Scanner(txtFile);
while (scanner.hasNext()){
String currentLine = scanner.nextLine();
Scanner scannerIn = new Scanner(currentLine);
if (currentLine.length()>1){
Vertex vertex1 = new Vertex(scannerIn.next());
Vertex vertex2 = new Vertex(scannerIn.next());
int weight = Integer.parseInt(scannerIn.next());
edges.add(new Edge(vertex1,vertex2,weight));
}
} }
@Override
public String toString() {
String result = "";
for (Edge edge:edges){
result = result+edge+"\n";
}
return result;
} /**
* The getEdges method returns the PriorityQueue of edges.
* @return -The Collection of edges (Priority Queue).
*/
public PriorityQueue<Edge> getEdges() {
return edges;
}
}import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.*;
import java.util.Map.Entry;public class RunAl {
private int shortest_2;
public static void main(String[] args) throws IOException {
runDijkstra(new File("bookgraph.txt"), "v1");
runDijkstra(new File("debuggraph.txt"),"a"); } /**
* Create an adjacency list (using the AdjacencyList constructor) from the given txtFile and run
* Dijkstra's algorithm with the given AdjacencyList and the given source vertex
*
* @param source
* @param txtFile
* @return
*/
public static Map<Vertex, Path> runDijkstra(File txtFile, String source) throws IOException {
Vertex startVertex = new Vertex(source);
AdjacencyList adjList = new AdjacencyList(txtFile);
Map<Vertex,Path> results = DjikstraAl.dijkstra(startVertex, adjList, source);
System.out.println("----- Dijkstra");
System.out.println("----------"+txtFile.getName()+", "+source);
Set<Entry<Vertex,Path>> entrySet = results.entrySet();
String pResult = "";
for (Entry<Vertex,Path> entry:entrySet){
pResult = pResult + entry.getKey()+": "+entry.getValue()+"\n";
}
System.out.println(pResult);
return results;
}
}读取的文件如下：n=1000 m=8544
0
25 244
108 275
140 273
159 313
219 199
254 392
369 171
518 271
538 250
568 253
603 307
613 196
638 3141
24 187
43 182
65 331
155 369
182 222
186 426
224 395
233 72
240 128
250 101
269 251
371 73
409 301
444 40
451 262
464 337
517 393
569 171
586 384
599 221
601 145
611 209
616 330
629 324
644 254
646 316
675 237
684 327
695 439
n是节点，m是边算法dijkstra二项堆
以下是我写的源码：package Dijkstra;public class Edge implements Comparable<Edge> {
private Vertex u, v;
private int weight; /**
* Comparable edge class based on weight. Order of u and v does not matter.
*
* @param u
* @param v
* @param weight
*/
public Edge(Vertex u, Vertex v, int weight) {
setU(u);
setV(v);
setWeight(weight);
} @Override
public int hashCode() {
return (u == null ? 0 : u.hashCode()) ^ (v == null ? 0 : v.hashCode())^ weight;
} @Override
public boolean equals(Object o) {
if (o instanceof Edge) {
Edge e = (Edge) o;
return weight == e.weight
&& ((u.equals(e.u) && v.equals(e.v)) || (u.equals(e.v) && v
.equals(e.u)));
} else {
return false;
}
} public int compareTo(Edge e) {
return weight - e.getWeight();
} public int getWeight() {
return weight;
} public void setWeight(int weight) {
this.weight = weight;
} public Vertex getU() {
return u;
} public void setU(Vertex u) {
this.u = u;
} public Vertex getV() {
return v;
} public void setV(Vertex v) {
this.v = v;
} public String toString() {
return "{(" + u + ", " + v + "): " + weight + "}";
}
}
package Dijkstra;public class Vertex { private int id;
private String name; /**
* A simple vertex class
*
* @param id
*/
Vertex(String name){
this.name = name;
} public String getName() {
return name;
} public String toString() {
return name;
} @Override
public boolean equals(Object o) {
if (o != null && o instanceof Vertex) {
Vertex v = (Vertex) o;
return name.equals(v.name);
} else {
return false;
}
} public int hashCode() {
return name.hashCode();
}}
package Dijkstra;import java.io.*;
import java.util.*;
import java.util.Map.Entry;public class AdjacencyList { private HashMap<Vertex, Map<Vertex, Integer>> adjList;
public AdjacencyList(File file) throws IOException{
adjList = new HashMap<Vertex, Map<Vertex, Integer>>();
Scanner scanner = new Scanner(file);
while (scanner.hasNext()){
String currentLine = scanner.nextLine();
Scanner scannerIn = new Scanner(currentLine);
if (currentLine.length()>1){
Vertex vertex1 = new Vertex(scannerIn.next());
Vertex vertex2 = new Vertex(scannerIn.next());
int weight = Integer.parseInt(scannerIn.next());
if (!adjList.containsKey(vertex1)){
adjList.put(vertex1, new HashMap<Vertex,Integer>());
}
if (!adjList.containsKey(vertex2)){
adjList.put(vertex2, new HashMap<Vertex,Integer>());
}
adjList.get(vertex1).put(vertex2, weight);
adjList.get(vertex2).put(vertex1, weight);
}
}
}
public Set<Entry<Vertex,Integer>> adjVertices(Vertex last){
return adjList.get(last).entrySet();
}
public String toString() {
String result = "";
Set<Entry<Vertex,Map<Vertex,Integer>>> set = adjList.entrySet();
for (Entry<Vertex,Map<Vertex,Integer>> entry:set){
result = result+entry.getKey()+":";
Map<Vertex,Integer> map = entry.getValue();
Set<Entry<Vertex,Integer>> adjVert = map.entrySet();
for (Entry<Vertex,Integer> vEntry:adjVert){
result = result+" ("+vEntry.getKey()+", "+vEntry.getValue()+")";
}
result = result+"\n";
}
return result;
}
public Map<Vertex, Map<Vertex, Integer>> getAdjList() {
return adjList;
}}package Dijkstra;
import java.util.LinkedList;public class Path implements Comparable<Path>{
/**
* The cumulative weight of the path.
*/
private int weight; /**
* The first and last vertices of the path.
*/
private Vertex start, end; /**
* The collection of edges that represent the path.
*/
private LinkedList<Edge> edges; /**
* Create an initial path where start and end are the given vertex
*
* @param vertex
* a vertex
*/
public Path(Vertex vertex) {
start = vertex;
end = vertex;
edges = new LinkedList<Edge>();
weight = 0;
} /**
* Assume that one of the vertices (either u or v) in the edge is the end vertex of old. Copies
* the old path and adds the edge e. (Make sure to update the end vertex, and weight correctly)
*
* @param old
* a path that ends in u or v
* @param e
* an edge between vertices u and v
*/
public Path(Path old, Edge e) {
LinkedList<Edge> edges = new LinkedList<Edge>(old.edges);
edges.add(e);
this.start = edges.getFirst().getU();
this.end = e.getV();
this.edges = edges;
for (int i=0;i<this.edges.size();i++){
weight += this.edges.get(i).getWeight();
}
} /**
* The compareTo method compares the cumulative weights of two Path objects
* @return -The integer representing the comparison between the two Path objects.
*/
@Override
public int compareTo(Path that) {
int result = 0;
if (this.weight<that.weight){
result = -1;
}
else if (this.weight>that.weight){
result = 1;
}
return result;
} /**
* The equals method compares two Path objects and determines whether they are equal by weight and
* instances of the start and end vertices.
* @param path -The Path object being compared.
* @return -The boolean value describing the two objects' equality.
*/
public boolean equals(Path path){
if (path.start.equals(this.start) && path.end.equals(this.end) && path.weight==this.weight){
return true;
}
return false;
} /**
* The toString method returns the string representation of the path. *Extra Credit*
* @return -The String representation of the path in the specified format.
*/
@Override
public String toString() {
String result = "";
if (start==end){
result = "["+weight+"] ("+start+")";
}
else{
result = "["+weight+"]";
for(Edge edge:edges){
result = result+" ("+edge.getU()+", "+edge.getV()+", "+edge.getWeight()+")";
}
}
return result;
} /**
* The getWeight method acts as a getter for the weight of the path.
* @return -The integer representing the weight of the path.
*/
public int getWeight() {
return weight;
} /**
* The getStart method acts as a getter for the starting (first) vertex of the path.
* @return -The Vertex object that is first in the path.
*/
public Vertex getStart() {
return start;
} /**
* The getEnd method acts as a getter for the ending (last) vertex of the path.
* @return -The Vertex object that is last in the path.
*/
public Vertex getEnd() {
return end;
} /**
* The getEdges method acts as a getter for the collection of edges (ArrayList).
* @return -The ArrayList of edges in the path.
*/
public LinkedList<Edge> getEdges() {
return edges;
}
}
package Dijkstra;import java.io.File;
import java.io.IOException;
import java.util.PriorityQueue;
import java.util.Scanner;public class EdgeList { /**
* The Collection object that holds the 'list' of edges.
*/
private PriorityQueue<Edge> edges; /**
*
* @param txtFile -The File object that contains the information necessary to create the list of edges.
* @throws IOException
*/
public EdgeList(File txtFile) throws IOException {
edges = new PriorityQueue<Edge>();
Scanner scanner = new Scanner(txtFile);
while (scanner.hasNext()){
String currentLine = scanner.nextLine();
Scanner scannerIn = new Scanner(currentLine);
if (currentLine.length()>1){
Vertex vertex1 = new Vertex(scannerIn.next());
Vertex vertex2 = new Vertex(scannerIn.next());
int weight = Integer.parseInt(scannerIn.next());
edges.add(new Edge(vertex1,vertex2,weight));
}
} }
@Override
public String toString() {
String result = "";
for (Edge edge:edges){
result = result+edge+"\n";
}
return result;
} /**
* The getEdges method returns the PriorityQueue of edges.
* @return -The Collection of edges (Priority Queue).
*/
public PriorityQueue<Edge> getEdges() {
return edges;
}
}import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.*;
import java.util.Map.Entry;public class RunAl {
private int shortest_2;
public static void main(String[] args) throws IOException {
runDijkstra(new File("bookgraph.txt"), "v1");
runDijkstra(new File("debuggraph.txt"),"a"); } /**
* Create an adjacency list (using the AdjacencyList constructor) from the given txtFile and run
* Dijkstra's algorithm with the given AdjacencyList and the given source vertex
*
* @param source
* @param txtFile
* @return
*/
public static Map<Vertex, Path> runDijkstra(File txtFile, String source) throws IOException {
Vertex startVertex = new Vertex(source);
AdjacencyList adjList = new AdjacencyList(txtFile);
Map<Vertex,Path> results = DjikstraAl.dijkstra(startVertex, adjList, source);
System.out.println("----- Dijkstra");
System.out.println("----------"+txtFile.getName()+", "+source);
Set<Entry<Vertex,Path>> entrySet = results.entrySet();
String pResult = "";
for (Entry<Vertex,Path> entry:entrySet){
pResult = pResult + entry.getKey()+": "+entry.getValue()+"\n";
}
System.out.println(pResult);
return results;
}
}读取的文件如下：n=1000 m=8544
0
25 244
108 275
140 273
159 313
219 199
254 392
369 171
518 271
538 250
568 253
603 307
613 196
638 3141
24 187
43 182
65 331
155 369
182 222
186 426
224 395
233 72
240 128
250 101
269 251
371 73
409 301
444 40
451 262
464 337
517 393
569 171
586 384
599 221
601 145
611 209
616 330
629 324
644 254
646 316
675 237
684 327
695 439
n是节点，m是边算法dijkstra二项堆
while (scanner.hasNext()){
String currentLine = scanner.nextLine();
Scanner scannerIn = new Scanner(currentLine);
if (currentLine.length()>1){....
或者Scanner scanner = new Scanner(txtFile);这样改下：
Scanner scanner = new Scanner(new FileInputStream(txtFile));