最短路径(Dijkstra)算法

目录

一、Dijkstra算法

二、核心思路

三、步骤

四、代码

一、Dijkstra算法

迪杰斯特拉(Dijkstra)算法是由荷兰计算机科学家狄克斯特拉于1959年提出的。是寻找从一个顶点到其余各顶点的最短路径算法，可用来解决最短路径问题。

二、核心思路

迪杰斯特拉算法采用贪心算法的策略，将所有顶点分为已标记点和未标记点两个集合，从起始点开始，不断在未标记点中寻找距离起始点路径最短的顶点，并将其标记，直到所有顶点都被标记为止。

所以我们需要准备一个起始点到其他点最短距离的一张表，和一个挑选节点的表,如下

		//从headnode出发到所有点最小距离的表
		//key: 从headnode出发到达key的点
		//value: 从headnode出发到达key的最小距离
		unordered_map<Node*, int> distanceMap;

		//先放入头节点，头节点到头节点的距离为0，其他为解锁的节点距离为正无穷
		distanceMap.insert(make_pair(headnode, 0));

		//有一个记录节点的表，使用完一个节点之后放入表中不再使用
		set<Node*> selectNodes;

需要注意的一点是该方法不能处理带有负权边的图，下面我们举出一个实例并通过迪杰斯特拉方法对其进行求解。

三、步骤

1、选一个minNode

2、考察minNode的所有边，判断边的toNode节点是否在set表中

3、如果不在表中，说明该点未被考察过，更新最小距离

4、在表中判断distanceMap中到该点的距离和现在走的这条路到该点的距离谁小，然后更新

5、重复1-4，直到所有的点被set表锁住结束整个流程

图解：

 重复上述步骤最终可以得到A点到所有点的最短路径的一个表 

四、代码

//Dijkstra的经典写法，有改写堆的优化
class Solution
{
public:
	unordered_map<Node*, int> dijkstra(Node* headnode) {
		//从headnode出发到所有点最小距离的表
		//key: 从headnode出发到达key的点
		//value: 从headnode出发到达key的最小距离
		unordered_map<Node*, int> distanceMap;

		//先放入头节点，头节点到头节点的距离为0，其他为解锁的节点距离为正无穷
		distanceMap.insert(make_pair(headnode, 0));

		//有一个记录节点的表，使用完一个节点之后放入表中不再使用
		set<Node*> selectNodes;

		//拿距离headnode最近并且没有被锁住的点
		Node* minNode = getMinNodeAndUnSelect(distanceMap, selectNodes);

		//一直更新minNode，直到最后所有点都被锁住，minNode == nullptr，所以完成整个流程
		while (minNode != nullptr) {
			int distance = distanceMap[minNode];
			for (auto edges : minNode->edges) {
				Node* toNode = edges->to;
				if (!selectNodes.count(toNode)) {
					distanceMap.insert(make_pair(toNode, distance + edges->weight));
				}
				distanceMap.insert(make_pair(toNode, min(distanceMap[toNode], distance + edges->weight)));
			}
			selectNodes.insert(minNode);
			minNode = getMinNodeAndUnSelect(distanceMap, selectNodes);
		}
		return distanceMap;
	}

	//返回距离headnode最近并且没有被锁过的点
	Node* getMinNodeAndUnSelect(unordered_map<Node*, int> distance, set<Node*> touchNode) {
		Node* minNode = nullptr;
		int minDistance = INT_MAX;
		for (auto pair : distance) {
			Node* getNode = pair.first;
			int getDistance = pair.second;
			if (!touchNode.count(minNode) && getDistance < minDistance) {
				minNode = getNode;
				minDistance = getDistance;
			}
		}
		return minNode;
	}
};