C最短路径Dijkstra算法如何实现

什么是Dijkstra算法

Dijkstra算法是求解图中单源最短路径的一种贪心算法。它能够找到源点到所有其他节点的最短路径，并且具有良好的时间复杂度。Dijkstra算法采用一种广度优先的搜索策略，与深度优先搜索不同，它使用一个集合S来存放已经求出最短路径的节点，而不是用一个队列来存放到达每个节点的路径。

template 
void Graph::Dijkstra(T startVertex) {
    unordered_set visited;
    priority_queue, vector>, greater>> pq;
    unordered_map dist;
    pq.push({startVertex, 0});
    for(auto vertex: adjacencyList) {
        dist[vertex.first] = INT_MAX;
    }
    dist[startVertex] = 0;

    while(!pq.empty()) {
        T temp = pq.top().first;
        pq.pop();
        visited.insert(temp);
        for(auto neighbor: adjacencyList[temp]) {
            if(visited.find(neighbor.first) == visited.end()) {
                int alt = dist[temp] + neighbor.second;
                if(alt < dist[neighbor.first]) {
                    dist[neighbor.first] = alt;
                    pq.push({neighbor.first, dist[neighbor.first]});
                }
            }
        }
    }
    PrintDistances(dist, startVertex);
}

Dijkstra算法的实现

Dijkstra算法的实现过程非常简单，主要分为以下几个步骤：

1. 创建一个集合S来存放已经求出最短路径的节点，以及一个优先队列pq。
2. 初始化源点startVertex的距离为0，其他顶点的距离为无穷大。
3. 将源点加入到pq中。
4. 从pq中取出dist最小的节点temp，将temp加入到S中。
5. 对temp的所有邻居，更新其距离值，如果修改后的距离值小于原来的距离值，则将该节点加入到pq中。
6. 重复步骤4和步骤5，直到pq为空。
7. 输出源点到各个节点的最短距离。

unordered_map> adjacencyList;

template 
void Graph::AddEdge(T u, T v, int weight) {
    adjacencyList[u][v] = weight;
}

template 
void Graph::PrintDistances(unordered_map& dist, T startVertex) {
    cout<<"Shortest distances from vertex "<