C++dijkstra算法

### Dijkstra算法的C++实现

#### 算法原理概述
Dijkstra算法用于解决单源最短路径问题，即给定图中的一个起点，求该点到其它各顶点的最短距离。此算法适用于边权重非负的情况。

#### 具体代码实现

##### graph类定义 (graph.h)

#ifndef GRAPH_H
#define GRAPH_H

#include <vector>
#include <limits>

class Graph {
public:
    explicit Graph(int vertices);
    void addEdge(int u, int v, int weight);
    std::pair<std::vector<int>, std::vector<int>> shortestPath(int src);

private:
    const int V;
    std::vector<std::vector<std::pair<int, int>>> adjList;

};

#endif //GRAPH_H

##### graph类成员函数定义 (graph.cpp)

#include "graph.h"
#include <queue>
#include <utility>

Graph::Graph(int vertices):V(vertices),adjList(V){}

void Graph::addEdge(int u, int v, int w){
    adjList[u].emplace_back(std::make_pair(v,w));
}

std::pair<std::vector<int>, std::vector<int>> Graph::shortestPath(int src) {
    std::priority_queue<std::pair<int,int>,
                        std::vector<std::pair<int,int>>,
                        std::greater<>> pq;
    
    std::vector<int> dist(V,std::numeric_limits<int>::max());
    std::vector<int> prev(V,-1); 

    dist[src]=0; 
    pq.push({dist[src],src});

    while (!pq.empty()){
        auto [distance,node] = pq.top();
        pq.pop();

        if(distance > dist[node]) continue;

        for(auto& edge : adjList[node]){
            int neighbor=edge.first;
            int newDist=distance+edge.second;

            if(newDist < dist[neighbor]){
                dist[neighbor]=newDist;
                prev[neighbor]=node;
                pq.emplace(dist[neighbor],neighbor);
            }
        }
    }

    return {dist,prev};
}

##### PathFinder 类定义 (pathfinder.h)

#ifndef PATHFINDER_H
#define PATHFINDER_H

#include "graph.h"

class PathFinder{
public:
    static void findShortestPaths(const Graph &g, int sourceVertex);
};

#endif //PATHFINDER_H

##### PathFinder 成员函数定义(pathfinder.cpp)

#include "pathfinder.h"
#include <iostream>

void PathFinder::findShortestPaths(const Graph &g, int sourceVertex){
    auto result=g.shortestPath(sourceVertex);
    auto distances=result.first;
    auto predecessors=result.second;

    std::cout << "Source Vertex ("<<sourceVertex<<")\n";
    for(size_t i=0;i<predecessors.size();++i){
        if(i==sourceVertex || predecessors[i]==-1 && i!=sourceVertex )continue;
        
        std::stack<int> path;
        for(int at=i;at!=-1;at=predecessors[at])
            path.push(at);
            
        std::cout<<"To vertex "<<i<<": ";
        while(!path.empty())
            std::cout<<path.top()<<" ",path.pop();   
        std::cout<<"\tDistance:"<<distances[i]<<'\n';
    }  
}

##### 主程序入口(main.cpp)

#include "pathfinder.h"

int main(){
    constexpr size_t numVertices{9}; // 假设有一个有九个节点的无向加权图
    
    Graph g(numVertices);
    // 添加一些边...
    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);

    PathFinder::findShortestPaths(g,0);

    return 0;
}

上述代码展示了如何利用优先队列优化后的Dijkstra算法来寻找从指定起始结点出发到达其余各个结点间的最小花费路径[^1]。通过`Graph`类管理图结构并提供核心逻辑；而`PathFinder`则负责展示最终的结果。最后，在`main()`函数里创建了一个具体的例子来进行验证测试[^2]。