• 单源最短路径算法之Dijkstra

    1、算法

    1. Dijkstra 算法必须指定一个 源点；
    2. 生成一个从源点到各个点的最小距离表，一开始只有一条记录，即源点到自己的最小距离为0，源点到其他所有点的最小距离都为正无穷大；
    3. 从距离表中取出没有访问过的记录里的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，不断重复这一步；
    4. 源点到所有点的记录如果都被访问一遍，过程停止，最小距离表就得到了。

    【要求】有向无负权重，可以有环。

    2、示例

    在这里插入图片描述
    选择a 作为源点。

    一开始，a 到每个点的最小距离表：

    abcde
    0∞∞∞∞

    选择表中的 a->a 距离为 0 的这条记录，通过 a 能到达 b、c 和 d，而 a->b 的距离 1 比最开始的无穷小，所以 a->b 的距离更新为 1，同理更新 a 到 c 和 d 的距离：

    abcde
    0162∞

    此时 a->a 这条边因为被访问过，所以接下来找到没有访问过的记录里的最小边 a->b。

    从 b 出发能到达 c （权重为1） 和 e （权重为6），而 a 通过 b 到达 c 的距离为 a->b->c = 1 + 2 = 3，比最小距离表中的 a->c 的 6 小，所以更新表中 a 到 c 的记录为 3。其他位置同理，于是得到更新后的最小距离表：

    abcde
    01327

    此时 a->b 这条边被访问过，所以在剩下的记录里挑选最小记录 a->d，从 d 出发到 e，a 通过 d 到达 e 的距离为12，比 a->e 的距离 7 大，所以不更新。

    后续操作类似。

    3、代码实现

    C++ 版

    //Dijkstra算法：初始版
class Dijkstra1 {
public:
    unordered_map<Vertex*, int> dijkstra(Vertex *from) {
        //记录源点到当前点Vertex* 的距离
        unordered_map<Vertex*, int> distanceMap;
        //初始化，点到自己的距离为0
        distanceMap[from] = 0;
        //选择过的点
        unordered_set<Vertex*> selectedVertexs;
        //map 中除了选择过的点外的记录最小的点
        Vertex* minVertex = getMinDistanceAndUnselectedVertex(distanceMap, selectedVertexs);

        while (minVertex != nullptr) {
            // 源点 到 minVertex(跳转点) 最小距离distance
            int distance = distanceMap[minVertex];
            for (Edge *edge : minVertex->adjE) {
                Vertex *toV = edge->to;

                if (!distanceMap.count(toV)) {
                    distanceMap[toV] = distance + edge->weight;
                } else {
                    distanceMap[toV] = min(distanceMap[toV], distance + edge->weight);
                }
            }
            selectedVertexs.insert(minVertex);
            minVertex = getMinDistanceAndUnselectedVertex(distanceMap, selectedVertexs);
        }

        return distanceMap;
    }

    //慢，每次都要遍历所有的记录选出最小的点进行发散，且还要过滤掉touchVertexs
    Vertex *getMinDistanceAndUnselectedVertex(unordered_map<Vertex*, int> &distanceMap, unordered_set<Vertex*> &touchVertexs) {
        Vertex *minVertex = nullptr;

        int minDistance = INT_MAX;

        for (auto &kv : distanceMap) {
            Vertex *vertex = kv.first;
            int distance = kv.second;
            if (!touchVertexs.count(vertex) && distance < minDistance) {
                minVertex = vertex;
                minDistance = distance;
            }
        }

        return minVertex;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    Java 版

    import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

// no negative weight
public class Dijkstra {

	public static HashMap<Node, Integer> dijkstra1(Node from) {
		HashMap<Node, Integer> distanceMap = new HashMap<>();
		distanceMap.put(from, 0); //初始化，点到点自己的距离为0
		// 打过对号的点
		HashSet<Node> selectedNodes = new HashSet<>();
        //map中除了打对号的点外的记录最小的点
		Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
		while (minNode != null) {
			//  原始点  ->  minNode(跳转点)   最小距离distance
			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 { // toNode ，更新最小距离表中的距离
					distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
				}
			}
			selectedNodes.add(minNode);
			minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
		}
		return distanceMap;
	}
	
    //慢，每次都要遍历所有的记录选出最小的记录的点进行发散，且还要过滤掉touchedNodes
	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) {
				minNode = node;
				minDistance = distance;
			}
		}
		return minNode;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    4、dijkstra算法优化

    利用 加强堆 ，当某个节点最短距离改变时做动态调整。

    C++ 版

    //Dijkstra算法：优化版
class Dijkstra2 {
public:
    class VertexRecord { //堆中的结构
    public:
        Vertex *v;
        int distance;

        VertexRecord(Vertex *v, int distance) {
            this->v = v;
            this->distance = distance;
        }
    };


    //加强堆
    class VertexHeap {
    private:
        //实际的堆结构
        vector<Vertex*> vertexs;
        //每个顶点在堆中的位置，反向索引表
        unordered_map<Vertex*, int> heapIndexMap;
        //key为顶点，value为从源点到该点的目前最小距离 （源点到当前点的距离）
        unordered_map<Vertex*, int> distanceMap;
        //堆上点的个数
        int size;

    public:
        VertexHeap(int _size) {
            vertexs.resize(_size);
            size = 0;
        }

        bool isEmpty() {
            return size == 0;
        }

        //有一个点叫vertex，现在发现了一个从源点出发到达vertex的距离为distance
        //判断要不要更新，如果需要的话，就更新
        void addOrUpdateOrIgnore(Vertex *vertex, int distance) {
            if (inHeap(vertex)) { //update
                distanceMap[vertex] = min(distanceMap[vertex], distance);
                insertHeapify(vertex, heapIndexMap[vertex]); //向上调整
            }

            //没有进入过堆，就是新增操作，add
            if (!isEntered(vertex)) {
                vertexs[size] = vertex;
                heapIndexMap[vertex] = size;
                distanceMap[vertex] = distance;
                insertHeapify(vertex, size++);
            }

            //ignore
        }

        //取出堆中的距离最小的记录
        VertexRecord* pop() {
            //取出距离最小的记录
            VertexRecord *vr = new VertexRecord(vertexs[0], distanceMap[vertexs[0]]);
            //交换0位置和最后一个位置的值
            swap(0, size - 1);
            //此时的size - 1位置的值修改为-1，用来表示删除，但不是真正地删除
            heapIndexMap[vertexs[size - 1]] = -1;
            distanceMap.erase(vertexs[size - 1]);

            //从堆上将该位置的值删掉 (C++此处需特别注意，因为是指针，所以不能随便清空内存)
            //free(vertexs[size - 1]);
            //vertexs[size - 1] = nullptr;

            //向下调整
            heapify(0, --size);

            return vr;
        }


        //堆中向上调整
        void insertHeapify(Vertex *vertex, int index) {
            while (distanceMap[vertexs[index]] < distanceMap[vertexs[(index - 1) / 2]]) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        //堆中向下调整
        void  heapify(int index, int size) {
            int left = index * 2 + 1;
            while (left < size) {
                int smallest = left + 1 < size && distanceMap[vertexs[left + 1]] < distanceMap[vertexs[left]] ? left + 1 : left;

                smallest = distanceMap[vertexs[smallest]] < distanceMap[vertexs[index]] ? smallest : index;

                if (smallest == index) break;

                swap(index, smallest);

                index = smallest;

                left = index * 2 + 1;
            }
        }

        //节点是否进入过堆
        bool isEntered(Vertex *v) {
            return heapIndexMap.count(v);
        }

        //比如(a, 0) 这个点在堆中处理完毕后，不要从heapIndexMap中删掉，而是将0改成-1，所以-1表示曾进来来但是出去了
        //是否在堆上：进来过且节点值不为-1
        bool inHeap(Vertex *vertex) {
            return isEntered(vertex) && heapIndexMap.count(vertex) != -1;
        }

        void swap(int ind1, int ind2) {
            heapIndexMap[vertexs[ind1]] = ind2;
            heapIndexMap[vertexs[ind2]] = ind1;
            Vertex *tmp = vertexs[ind1];
            vertexs[ind1] = vertexs[ind2];
            vertexs[ind2] = tmp;
        }
    };

    //从start出发，所有start能到达的顶点，生成到达每个顶点的最小路径并返回
    unordered_map<Vertex*, int> dijkstra(Vertex *start, int size) {

        VertexHeap *vH = new VertexHeap(size);

        //如果记录是之前没有的就add，记录是之前就有的就update，记录是已经收集过的就ignore
        vH->addOrUpdateOrIgnore(start, 0);

        //start出发到每个顶点的距离表result
        unordered_map<Vertex*, int> result;

        while (!vH->isEmpty()) {
            VertexRecord *vr = vH->pop();
            Vertex *cur = vr->v;
            int distance = vr->distance;
            //查看是否能调整其他顶点的记录
            for (Edge *edge : cur->adjE) {
                vH->addOrUpdateOrIgnore(edge->to, edge->weight + distance);
            }
            result[cur] = distance;
        }
        return result;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147

    Java 版

    public class Dijkstra {
	//===============优化版本
    //每次调整更新最小距离，且将其重新放入堆中
	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; // 实际的堆结构
		// key 某一个node， value 上面堆中的位置 (记录每个点在堆中的位置)  反向索引表
		private HashMap<Node, Integer> heapIndexMap; 
		// key 某一个节点， value 从源节点出发到该节点的目前最小距离 （源点到当前点的距离）
		private HashMap<Node, Integer> distanceMap;
		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;
		}

		// 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
		// 判断要不要更新，如果需要的话，就更新
		public void addOrUpdateOrIgnore(Node node, int distance) {
			if (inHeap(node)) { //update
				distanceMap.put(node, Math.min(distanceMap.get(node), distance));
				insertHeapify(node, heapIndexMap.get(node)); //往上调整
			}
			if (!isEntered(node)) { //没有进入过 新增操作 add
				nodes[size] = node;
				heapIndexMap.put(node, size);
				distanceMap.put(node, distance);
				insertHeapify(node, size++);
			}
            //ignore
		}

		public NodeRecord pop() { //取出距离最小的记录
			NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
			swap(0, size - 1); //先交换0位置和最后一个位置的值 0 -> size-1，size-1 -> 0
			heapIndexMap.put(nodes[size - 1], -1); //将此时的size-1位置的值修改为-1，用来表示删除，但不是真正地删除
			distanceMap.remove(nodes[size - 1]);
			// free C++同学还要把原本堆顶节点析构，对java同学不必
			nodes[size - 1] = null; //从堆上将该位置的值删掉
			heapify(0, --size); //往下调整
			return nodeRecord;
		}

		private void insertHeapify(Node node, 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);
		}

        //比如(a,0) 这个点在堆中处理完毕后，不要从headpIndexMap中删掉，而是将0改成-1，所以-1就表示曾经进来过但是出去了
        //是否在堆上：进来过且节点值不为-1
		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;
		}
	}

	// 改进后的dijkstra算法
	// 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
	public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
		NodeHeap nodeHeap = new NodeHeap(size);
		nodeHeap.addOrUpdateOrIgnore(head, 0); //如果记录是之前没有的就add，记录是之前就有的就update，记录是已经收集过的就ignore
		HashMap<Node, Integer> result = new HashMap<>(); //head出发到每个点的距离表result
		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;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120

    5、测试代码

    int main() {
	vector<vector<int> > infos2 {
		//边信息：{权重，起点，终点}
        {1, 1, 2},
        {6, 1, 3},
        {2, 1, 4},
        {2, 2, 3},
        {5, 3, 4},
        {6, 2, 5},
        {1, 3, 5},
        {10, 4, 5},
    };
    //实现见https://blog.csdn.net/u011386173/article/details/126275411?spm=1001.2014.3001.5501
    GraphGenerator *gg = new GraphGenerator();
    Graph *g2 = gg->createGraph(infos2);

    cout << "Dijkstra1 : " << endl;
    Dijkstra1 *dj1 = new Dijkstra1();
    unordered_map<Vertex*, int> result2 = dj1->dijkstra(g2->vertexs[1]);
    for (auto &kv : result2) {
        cout << "[" << kv.first->value << ", "<<  kv.second << "]" << endl;
    }


    cout << "Dijkstra2 : " << endl;
    Dijkstra2 *dj2 = new Dijkstra2();
    unordered_map<Vertex*, int> result3 = dj2->dijkstra(g2->vertexs[1], 5);
    for (auto &kv : result3) {
        cout << "[" << kv.first->value << ", " << kv.second << "]" << endl;
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
  • 相关阅读:
    第二十八章 管理许可（一）
    exec函数族
    IDEA 设置 Git 在左侧展示
    【Python】构建一个智能图书管理系统
    SAP Success Factor Single Sign On(单点集成) 的文档清单
    Java线程池是个什么东西？核心原理又是什么？
    【springboot】各种条件注解与源码分析
    整理了25个Python文本处理案例，收藏！
    vue3学习笔记
    某大厂面试题：说一说Java、Spring、Dubbo三者SPI机制的原理和区别
  • 原文地址：https://blog.csdn.net/u011386173/article/details/126469523