迪杰斯特拉算法C++

迪杰斯特拉(Dijkstra) 算法是一种用于解决单源最短路径问题的经典图算法。它能够找出从一个特定的起始顶点到图中其他所有顶点之间的最短路径。该算法适用于非负权值的情况，并且常应用于网络路由、地图导航等领域。

### C++ 实现基本步骤：

#### 1. 定义结构体或类表示图的边和顶点

struct Edge {
    int to;
    double weight;
};

struct Vertex {
    std::vector<Edge> adjacents; // 邻接边列表
};

#### 2. 初始化数据结构
通常需要一个 `std::map` 来记录每个顶点的距离以及是否已被访问的状态。假设我们有 `std::unordered_map<int, pair<double, bool>> distAndVisited`，其中 `int` 表示顶点编号，`pair<double, bool>` 包含当前已知的距离和是否已经被访问。

#### 3. 实现迪杰斯特拉算法的核心函数

void dijkstra(std::unordered_map<int, pair<double, bool>>& distAndVisited, const std::vector<Vertex>& graph, int startVertex) {
    for (const auto& vertex : graph) {
        distAndVisited[vertex.id] = {std::numeric_limits<double>::max(), false}; // 初始设置距离无穷大，未访问
    }
    
    distAndVisited[startVertex].first = 0.0; // 起始节点的距离设为0

    while (!distAndVisited.empty()) {
        int currentVertex = -1;
        double minDistance = std::numeric_limits<double>::max();
        
        // 找出下一个处理的节点，即待处理节点中未访问且距离最小的节点
        for (const auto& it : distAndVisited) {
            if (!it.second.second && it.first != startVertex && it.second.first < minDistance) {
                minDistance = it.second.first;
                currentVertex = it.first;
            }
        }

        // 如果所有节点都被访问过，则结束循环
        if (currentVertex == -1) break;

        // 标记当前节点为已访问
        distAndVisited[currentVertex].second = true;

        for (const auto& edge : graph[currentVertex].adjacents) {
            int nextVertex = edge.to;
            double newDistance = distAndVisited[currentVertex].first + edge.weight;

            // 更新相邻节点的距离如果更小
            if (newDistance < distAndVisited[nextVertex].first) {
                distAndVisited[nextVertex].first = newDistance;
            }
        }
    }
}

#### 4. 使用示例

#include <iostream>
#include <vector>
#include <unordered_map>
#include <limits>

// ... 以上定义的结构体和函数 ...

int main() {
    // 构建图的实例，添加边和顶点信息
    std::vector<Vertex> graph = {/* 添加顶点和边 */};

    // 执行迪杰斯特拉算法
    dijkstra(distAndVisited, graph, 0); // 假设起始点为0
    
    // 输出结果，例如打印从起点到其他所有顶点的最短距离
    for (const auto& vertex : distAndVisited) {
        std::cout << "Vertex " << vertex.first << ": Distance = " << vertex.second.first << std::endl;
    }

    return 0;
}

### 相关问题:

1. **迪杰斯特拉算法如何处理带负权重的图？**
- 对于包含负权重边的图，迪杰斯特拉算法无法保证找到正确的解。在这种情况下，可以考虑使用贝尔曼-福特算法。

2. **为什么需要初始化所有顶点的距离为无穷大？**
- 初始化为无穷大的目的是为了确保从起始节点开始计算距离，而初始状态下的距离未知。这有助于算法正确地计算并更新每个顶点的新距离。

3. **在实际应用中，迪杰斯特拉算法还有哪些限制？**
- 主要是关于时间复杂度和内存消耗。在大规模图上运行可能会导致性能瓶颈，此外，算法本身并不适合实时系统或对响应时间有极高要求的应用场景。