swim-fish 2015-05-22 15:00 采纳率: 0%
浏览 1362
已结题

使用dijkstra求最短路径,动态添加数据,无法求出最短路径

package Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

import com.test.Station;

public class DijSuccess {
public static int INFINITY = 99999;
public static Map vertexMap = new HashMap();

// 边距
public static class Edge {
    public Vertex dest;
    public double cost;

    public Edge(Vertex d, double c) {
        this.dest = d;
        this.cost = c;
    }

}

// 静态类:Vertex
public static class Vertex implements Comparable<Vertex> {
    public String name;
    public List<Edge> adj;
    public double dist;
    public Vertex prev;
    public int scratch;
    public boolean visited;

    public Vertex(String nm) {
        this.name = nm;
        adj = new ArrayList<Edge>();
        reset();
    }

    public void reset() {
        visited = false;
        dist = DijSuccess.INFINITY;
    }

    @Override
    public int compareTo(Vertex o) {
        double c = o.dist;

        return dist < c ? -1 : dist > c ? 1 : 0;
    }

}

// dijkstra算法实现:找到从startName点出发,到其他所有点的最短路径:选取自己定义的终点
public static void dijkstra(String startName, String endName) {
    PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();// 该队列以权值升序排列,因为Vertex实现Comparable接口
    Vertex start = vertexMap.get(startName);
    start.dist = 0;
    for (Vertex v : vertexMap.values())
        pq.add(v);
    int seenNum = 0;
    while (!pq.isEmpty() && seenNum < vertexMap.size()) {
        Vertex v = pq.remove();
        if (v.name.equals(endName)) { // 恰好是自己要找的那个点
            System.out.println(startName + "---->" + v.name + ":" + v.dist);
            System.out.println(getPreNames(v));
            break;

        }
        if (v.scratch != 0)
            continue;
        v.scratch = 1;
        seenNum++;

        for (Edge e : v.adj) {
            Vertex w = e.dest;
            double v_to_w = e.cost;
            if (w.dist > v.dist + v_to_w) {
                w.dist = v.dist + v_to_w;
                w.prev = v;
                pq.remove(w);// 出队
                pq.add(w);// 按优先级插在队头,先插入的在队头,依次往后

            }
        }
    }
    while (pq.peek() != null) {
        pq.poll();
    }
}

/**
 * 得到最短路径所经历的路线 seven
 * 
 * @param v
 * @return
 */
public static String getPreNames(Vertex v) {
    String routeEndName = v.name;
    StringBuilder sb = new StringBuilder();
    while (v.prev != null) {
        sb.append(v.prev.name + ",");
        v = v.prev;
    }
    String reverseRoute = routeEndName + "," + sb.toString();
    String[] reverseArray = reverseRoute.split(",");
    StringBuilder route = new StringBuilder();

    for (int i = 0; i < reverseArray.length; i++) {
        route.append(reverseArray[reverseArray.length - 1 - i]);
        route.append(",");
    }
    return route.substring(0, route.length() - 1);
}

public static void main(String[] args) {
    // Vertex v1 = new Vertex("v1");
    // Vertex v2 = new Vertex("v2");
    // Vertex v3 = new Vertex("v3");
    // Vertex v4 = new Vertex("v4");
    // Vertex v5 = new Vertex("v5");
    //
    // List<Edge> e1l = v1.adj;
    // List<Edge> e2l = v2.adj;
    // List<Edge> e3l = v3.adj;
    // List<Edge> e4l = v4.adj;
    // List<Edge> e5l = v5.adj;
    //
    // Edge e12 = new Edge(v2, 10);
    // Edge e14 = new Edge(v4, 30);
    // Edge e15 = new Edge(v5, 100);
    // e1l.add(e14);
    // e1l.add(e15);
    // e1l.add(e12);
    //
    // Edge e23 = new Edge(v3, 50);
    // e2l.add(e23);
    //
    // Edge e35 = new Edge(v5, 10);
    // e3l.add(e35);
    //
    // Edge e43 = new Edge(v3, 20);
    // Edge e45 = new Edge(v5, 60);
    // e4l.add(e43);
    // e4l.add(e45);
    // vertexMap.put("v1", v1);
    // vertexMap.put("v2", v2);
    // vertexMap.put("v3", v3);
    // vertexMap.put("v4", v4);
    // vertexMap.put("v5", v5);
    //
    // dijkstra("v2", "v5");
    List<Station> stations = new ArrayList<Station>();
    for (int i = 0; i < 5; i++) {
        Station station = new Station();
        station.setCurrentstation("v" + i);
        List<Station> nextStations = new ArrayList<Station>();
        for (int j = i + 1; j < 5; j++) {
            Station station2 = new Station();
            station2.setCurrentstation("v" + j);
            nextStations.add(station2);
        }
        station.setNextStations(nextStations);
        stations.add(station);
    }

    for (Station station : stations) {
        // 添加根节点
        Vertex v1 = new Vertex(station.getCurrentstation());
        List<Edge> e11 = v1.adj;
        vertexMap.put(station.getCurrentstation(), v1);
        // 添加子节点
        int i=0;
        for (Station station2 : station.getNextStations()) {
            Vertex v2 = new Vertex(station2.getCurrentstation());
            Edge e1 = new Edge(v2,i);
            e11.add(e1);
            i++;
            vertexMap.put(station2.getCurrentstation(), v2);
        }
    }
    dijkstra("v0", "v4");
}

}

  • 写回答

1条回答 默认 最新

  • _1_1_7_ 2016-06-06 07:45
    关注

    调用一次dijkstra后,对象的状态都改变了,在动态添加完节点,至少要重置一下对象的状态吧。

    评论

报告相同问题?

悬赏问题

  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常