最短路径算法 Dijkstra

有向图、无负权重、有环

1. 先用一个表格记录 a 到其余点的距离，初始值是 a 到 a 的距离为 0，与其余点距离正无穷，从 a 点（起点）开始计算
2. 从 A 出发看可以直接到达的点距离为多少，接着获得距离更新表，有 B，C，D，如果比原来的值小，就更新。锁定 A 点，然后用 B，C，D 其中一个点为起点再出发找最近的点，如果有更短的路径就更新（已经确定的答案不碰，在所有未确定的路中找最短）
3. 当所有的点都锁死时候，就返回了。

public static HashMap<Node, Integer> dijksttra(Node from) {
  HashMap<Node, Integer> distanceMap = new HashMap<>();
  distanceMap.put(from, 0);
  // 打过对号的点
  HashSet<Node> selectedNodes = new HashSet<>();
  Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); // 找到最小距离的条点（未打钩
  while (minNode != null) {
    int distance = distanceMap.get(minNode);
    for (Edge edge : minNode.edges) {
      Node toNode = edge.to;
      if (!distanceMap.containsKey(toNode))
        distanceMap.put(toNode, distance + edge.weight);
      else
        distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
    }
    selectedNodes.add(minNode);
    minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); // 找到最小距离的条点（未打钩
  }

  return distanceMap;
}

public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
  Node minNode = null;
  int minDistance = Integer.MAX_VALUE;
  for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
    Node node = entry.getKey();
    int distance = entry.getValue();
    if (!touchedNodes.contains(node) && distance < minDistance) {
      minDistance = distance;
      minNode = node;
    }
  }
  return minNode;
}

使用加强堆优化 #

大根堆结构

public static class NodeRecord {
  public Node node;
  public int distance;

  public NodeRecord(Node node, int distance) {
    this.node = node;
    this.distance = distance;
  }
}

public static class NodeHeap {
  private Node[] nodes;// 实际的堆结构
  private HashMap<Node, Integer> heapIndexMap;// key 某个node value 堆中的位置
  private HashMap<Node, Integer> distanceMap;// key某个节点 value 从源出发到该节点目前最小距离
  private int size;// 堆上有多少个点

  public NodeHeap(int size) {
    nodes = new Node[size];
    heapIndexMap = new HashMap<>();
    distanceMap = new HashMap<>();
    size = 0;
  }

  public boolean isEmpty() {
    return size == 0;
  };

  public void addOrUpdateOrIgnore(Node node, int distance) {
    if (inHeap(node)) {
      distanceMap.put(node, Math.min(distanceMap.get(node), distance));
      insertHeapify(heapIndexMap.get(node));
    }
    if (!isEntered(node)) {
      nodes[size] = node;
      heapIndexMap.put(node, size);
      distanceMap.put(node, distance);
      insertHeapify(size++);
    }
  }

  public NodeRecord pop() {
    NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
    swap(0, size - 1);
    heapIndexMap.put(nodes[size - 1], -1);
    distanceMap.remove(nodes[size - 1]);
    nodes[size - 1] = null;
    heapify(0, --size);
    return nodeRecord;
  }

  private void insertHeapify(int index) {
    while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
      swap(index, (index - 1) / 2);
      index = (index - 1) / 2;
    }
  }

  private void heapify(int index, int size) {
    int left = index * 2 + 1;
    while (left < size) {
      int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
          ? left + 1
          : left;
      smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
      if (smallest == index) {
        break;
      }
      swap(smallest, index);
      index = smallest;
      left = index * 2 + 1;
    }
  }

  private boolean isEntered(Node node) {
    return heapIndexMap.containsKey(node);
  }

  private boolean inHeap(Node node) {
    return isEntered(node) && heapIndexMap.get(node) != -1;
  };

  private void swap(int index1, int index2) {
    heapIndexMap.put(nodes[index1], index2);
    heapIndexMap.put(nodes[index2], index1);
    Node tmp = nodes[index1];
    nodes[index1] = nodes[index2];
    nodes[index2] = tmp;
  }
}

代码

public static HashMap<Node, Integer> dijkstra(Node head, int size) {
    NodeHeap nodeHeap = new NodeHeap(size);
    nodeHeap.addOrUpdateOrIgnore(head, 0);
    HashMap<Node, Integer> result = new HashMap<>();
    while (!nodeHeap.isEmpty()) {
      NodeRecord record = nodeHeap.pop();
      Node cur = record.node;
      int distance = record.distance;
      for (Edge edge : cur.edges) {
        nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
      }
      result.put(cur, distance);
    }
    return result;
  }