Java利用Dijkstra演演算法求解拓撲關係最短路徑

 
import com.gis.spacedata.domain.entity.tunnel.TunnelTopologyRelEntity;
import lombok.extern.slf4j.Slf4j;
 
import java.util.*;
 
@Slf4j
public class PathUtil {
 
 
    /**
     * 方法描述: 求最短路徑
     *
     */
    public static List<Long> dijkstra(List<TunnelTopologyRelEntity> topologies, long start, long end) {
        int size=topologies.size();
        Map<String, Double> distMap = new HashMap<>(size);
        //存放源節點到各個節點的距離key 目標節點，value 源節點到該節點的距離
        Map<Long, Double> dists = new HashMap<>(size);
        //key: 當前節點，value：從原點到達key的最短路徑的前驅（上一個）節點
        Map<Long, Long> parent = new HashMap<>(size);
        //被標記最短距離的節點
        Set<Long> markNodes = new HashSet<>(size);
        //獲取所有節點列表
        Set<Long> nodes = new HashSet<>(10);
        for (TunnelTopologyRelEntity e : topologies) {
            nodes.add(e.getSource());
            nodes.add(e.getTarget());
            distMap.put(e.getSource() + "-" + e.getTarget(), e.getCost());
        }
        //初始化各個節點到源節點的距離
        for (long node : nodes) {
            if (node == start) {
                dists.put(node, 0d);
            } else {
                dists.put(node, getCost(distMap, start, node));
            }
        }
        // 不斷迭代
        while (true) {
            //距離源節點距離最近的節點(還未被標記為離源節點最近的點)
            long closestNode = -1;
            double min = Double.MAX_VALUE;
            for (Map.Entry<Long, Double> entry : dists.entrySet()) {
                if (entry.getValue() < min && !markNodes.contains(entry.getKey())) {
                    min = entry.getValue();
                    closestNode = entry.getKey();
                }
            }
            // 找不到可達的路徑了或到達目標點
            if (closestNode == -1 || closestNode==end) {
                break;
            }
            markNodes.add(closestNode);
            for (long node : nodes) {
                double dist = getCost(distMap, closestNode, node);
                // 找到一個為擴充套件的子節點
                if (dist > 0 && !markNodes.contains(node)) {
                    double new_dist = dists.get(closestNode) + dist;
                    // 新距離小於原始距離，更新
                    if (new_dist < dists.get(node)) {
                        dists.put(node, new_dist);
                        parent.put(node, closestNode);
                    }
                }
            }
        }
        // 倒敘查詢到路徑
        if (dists.get(end) == Integer.MAX_VALUE) {
            log.info(start + "到" + end + "之間沒有最短路徑");
            return null;
        } else {
            List<Long> path = new ArrayList<>();
            long current = end;
            path.add(current);
            while (current != start) {
                current = parent.get(current);
                path.add(current);
            }
            //反轉
            Collections.reverse(path);
            return path;
        }
    }
 
    /**
     * 方法描述: 獲取相鄰節點之間距離
     *
     */
    private static double getCost(Map<String, Double> distMap, long start, long end) {
        if (start == end) {
            return 0;
        }
        Double dist1 = distMap.get(start + "-" + end);
        if (dist1 != null) {
            return dist1;
        }
        Double dist2 = distMap.get(end + "-" + start);
        if (dist2 != null) {
            return dist2;
        }
        return Double.MAX_VALUE;
    }
 
 
}

public List<Long> getPointShortWay(String startCode, String endCode) {
        TunnelTopologyCodeRelEntity startTopologyCodeRel = getTopologyCodeRel(startCode);
        TunnelTopologyCodeRelEntity endTopologyCodeRel = getTopologyCodeRel(endCode);
        if (Func.isNull(startTopologyCodeRel) || Func.isNull(endTopologyCodeRel)) {
            return Collections.emptyList();
        }
        List<TunnelTopologyRelEntity> list=list();
        return PathUtil.dijkstra(list,startTopologyCodeRel.getId(), endTopologyCodeRel.getId());
    }