不引用迪杰斯特拉算法的库，实现迪杰斯特拉算法的C++代码

C++实现Dijkstra算法的基本步骤不依赖于特定库，下面是一个简单的示例，展示了如何手动实现这个算法[^1]：

#include <vector>
#include <queue>
#include <limits>

using namespace std;

// 边结构体
struct Edge {
    int destination;
    int weight;
};

// 顶点类，包含距离和标记
class Vertex {
public:
    int distance = INT_MAX; // 初始距离设为无穷大
    bool visited = false;   // 标记是否已访问

    // 构造函数
    Vertex(int initialDistance) : distance(initialDistance) {}
};

// 求最短路径
void dijkstra(vector<Edge>& graph, int start) {
    priority_queue<pair<int, Vertex>, vector<pair<int, Vertex>>, greater<pair<int, Vertex>>> pq; // 使用堆来存储待处理的顶点
    pq.push({0, start}); // 开始节点的距离设为0，添加到堆中

    while (!pq.empty()) {
        auto current = pq.top(); // 取出当前最小距离的节点
        pq.pop();

        if (current.second.distance != INT_MAX) { // 如果节点已被标记为已访问，则跳过
            if (current.first > current.second.distance) {
                current.first = current.second.distance; // 更新距离
            }

            // 更新与当前节点相邻的未访问节点的距离
            for (const auto& edge : graph[current.second.destination]) {
                if (!edge.source.visited && edge.weight + current.first < edge.source.distance) {
                    edge.source.distance = edge.weight + current.first;
                    pq.push({edge.source.distance, edge.source});
                }
            }
        }
    }
}

int main() {
    // 示例图的边和顶点
    vector<Edge> edges = {{1, 4}, {2, 8}, {3, 7}};
    vector<Vertex> vertices = {Vertex(0), Vertex(∞), Vertex(∞), Vertex(∞)};
    
    dijkstra(edges, 0); // 从节点0开始执行算法

    return 0;
}