最短路径算法对于有17个顶点24条边的图代码怎么弄

Question

我找到的代码都是用十个顶点以下的，对于顶点过多或者边过多，运行不了，还有大于十个顶点图，每个顶点怎么命名，0123456789好像不好使

Answer 1

引自免费微信小程序：皆我百晓生

在解决这个问题之前，我们需要先明确你想要使用的具体最短路径算法。这里我将展示如何使用Dijkstra算法实现一个适用于任意顶点数的图，并处理大量的边。Dijkstra算法是一种用于寻找图中两点间最短路径的算法。

首先，你需要定义一个表示图的数据结构。我们可以使用邻接矩阵或者邻接表来存储图的信息。这里我选择邻接表作为例子，因为对于稀疏图（边的数量远小于顶点数量的平方），它更节省空间。

以下是使用C++实现的一个简单版本的Dijkstra算法：

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

// 用于存储顶点信息
struct Vertex {
    int id;
};

// 用于存储边信息，包含起始顶点、结束顶点和权重
struct Edge {
    int from, to, weight;
};

// 邻接表，用于存储图的结构
using AdjacencyList = std::vector<std::vector<Edge>>;

// Dijkstra算法实现
std::pair<int, std::vector<Vertex*>> dijkstra(const AdjacencyList& graph, Vertex* start) {
    const int numVertices = graph.size();
    std::vector<int> distances(numVertices, std::numeric_limits<int>::max());
    std::vector<Vertex*> parents(numVertices, nullptr);
    std::priority_queue<std::pair<int, Vertex*>, std::vector<std::pair<int, Vertex*>>, std::greater<std::pair<int, Vertex*>>> pq;

    distances[start->id] = 0;
    pq.push({0, start});

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

        if (currentDistance > distances[currentVertex->id]) continue; // 已经更新过更优的距离

        for (const auto& edge : graph[currentVertex->id]) {
            int neighborId = edge.to;
            int newDistance = currentDistance + edge.weight;

            if (newDistance < distances[neighborId]) {
                distances[neighborId] = newDistance;
                parents[neighborId] = currentVertex;
                pq.push({newDistance, graph[neighborId][0].to}); // 使用第一个邻居作为指向，简化代码，实际应用中可以使用更复杂的数据结构
            }
        }
    }

    return {distances.back(), parents};
}

int main() {
    // 创建一个17个顶点24条边的图
    AdjacencyList graph(17);

    // 添加边，例如：
    graph[0].push_back({0, 1, 5});
    graph[0].push_back({0, 4, 2});
    // ... 其他边

    // 初始化顶点
    std::vector<Vertex> vertices(17);
    for (int i = 0; i < 17; ++i) {
        vertices[i].id = i;
    }

    // 找出从第0号顶点到其他顶点的最短路径
    auto result = dijkstra(graph, &vertices[0]);
    std::cout << "Shortest distance to vertex " << result.first << std::endl;

    // 输出最短路径，如果需要
    std::vector<Vertex*> shortestPath(result.second.begin() + 1, result.second.end()); // 忽略起点
    std::cout << "Shortest path: ";
    for (auto v : shortestPath) {
        std::cout << v->id << " -> ";
    }
    std::cout << vertices[result.second.back()]->id << std::endl;

    return 0;
}

这段代码实现了Dijkstra算法并给出了一个简单的示例。你需要根据实际情况填充graph中的边。注意，这个实现没有考虑负权边，如果你的图中有负权边，需要使用Bellman-Ford算法或者Johnson's算法。

另外，关于顶点命名的问题，我在这里使用了简单的整数编号（0-16）。你可以根据需求为顶点添加额外的信息，比如字符串标识。在这个例子中，我们只关心顶点之间的关系，所以编号就足够了。如果你需要显示顶点名称，只需在Vertex结构体中添加一个字符串成员即可。