graph.java

本代码可以用于查找指定地图中点与点之间的最短路径

package shortestpath;

import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Collection;
import java.util.List;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.NoSuchElementException;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2007</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */

public class Graph {

  public static final double INFINITY = Double.MAX_VALUE;

  //在图上添加一条边
  public void addEdge(String sourceName, String destName, double cost) {
    Vertex v = getVertex(sourceName);
    Vertex w = getVertex(destName);
    v.adj.add(new Edge(w, cost));
  }

  private Vertex getVertex(String vertexName) {
    Vertex v = (Vertex) vertexMap.get(vertexName);
    if (v == null) {
      v = new Vertex(vertexName);
      vertexMap.put(vertexName, v);
    }
    return v;
  }

  private Map vertexMap = new HashMap(); //
  //打印最短路径的方法

  private String[] printPath(Vertex dest) {
    String shortestpath[] = new String[66];
    String[] path = new String[66];
    int i = 0;
    while (dest != null) {
      shortestpath[i++] = dest.name;
      dest = dest.prev;
    }
    for (int j = 0; j < i; j++) {
      path[j] = shortestpath[i - j - 1];
    }
    return path;
  }

  public String[] printPath(String destName) {
    Vertex w = (Vertex) vertexMap.get(destName);
    String[] path1 = new String[66];
    if (w == null) {
      throw new NoSuchElementException();
    }
    else if (w.dist == INFINITY) {
      System.out.print(destName + " is unreachable");
    }
    else {
      System.out.print("(Cost is: " + w.dist + ")");
      path1 = printPath(w);
    }
    return path1;
  }

  //用来初始化最短路径算法中使用的数据成员的私有方法
  private void clearAll() {
    Iterator itr = vertexMap.values().iterator();
    while (itr.hasNext()) {
      ( (Vertex) itr.next()).reset();
    }
  }

  //Dijkstra算法
  public void Dijkstra(String startName) {
    PriorityQueue pq = new PriorityQueue();
    Vertex start = (Vertex) vertexMap.get(startName);
    if (start == null) {
      throw new NoSuchElementException("Start vertex not found");
    }
    clearAll();
    pq.add(new Path(start, 0));
    start.dist = 0;

    int nodesSeen = 0;
    while (!pq.isEmpty() && nodesSeen < vertexMap.size()) {
      Path vrec = (Path) pq.remove();
      Vertex v = vrec.dest;
      if (v.scratch != 0) {
        continue;
      }

      v.scratch = 1;
      nodesSeen++;
      for (Iterator itr = v.adj.iterator(); itr.hasNext(); ) {
        Edge e = (Edge) itr.next();
        Vertex w = e.dest;
        double cvw = e.cost;
        if (cvw < 0) {
          throw new GraphException("Graph has negative edges");
        }
        if (w.dist > v.dist + cvw) {
          w.dist = v.dist + cvw;
          w.prev = v;
          pq.add(new Path(w, w.dist));
        }
      }
    }
  }

  public Graph() {
  }

  static String[] RoadFinder(String startName, String destName) {
    Graph g = new Graph();
    String[] path2 = new String[66];
    int index = 0;
    try {
      FileReader fin = new FileReader(
          "citydistance.txt");
      BufferedReader graphFile = new BufferedReader(fin);
      //读入边并插入
      String line;

      while ( (line = graphFile.readLine()) != null) {
        StringTokenizer st = new StringTokenizer(line);
        try {
          if (st.countTokens() != 3) {
            System.out.println("Skipping bad line" + line);
            continue;
          }
          String source = st.nextToken();
          String dest = st.nextToken();
          double cost = Double.parseDouble(st.nextToken());
          g.addEdge(source, dest, cost);
        }
        catch (NumberFormatException e) {
          System.out.println("Skipping bad line" + line);
        }
      }
    }
    catch (IOException e) {
      System.err.println(e);
    }
    System.out.println("File read……");
    System.out.println("共有" + g.vertexMap.size() + "个地点");
    try {
      g.Dijkstra(startName);
      path2 = g.printPath(destName);

    }

    catch (NoSuchElementException e) {
      System.err.println(e);
    }
    catch (GraphException e) {
      System.err.println(e);
    }

    return path2;
  }

}