阅读量:0
在C++中，可以使用邻接矩阵或邻接表来表示图，并实现Dijkstra算法。以下是使用邻接表表示图的示例代码：
#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; struct Node { int dest; int weight; }; class Graph { private: int V; vector<vector<Node>> adjList; public: Graph(int vertices) { V = vertices; adjList.resize(V); } void addEdge(int src, int dest, int weight) { Node node = { dest, weight }; adjList[src].push_back(node); } void dijkstra(int src) { vector<int> dist(V, INT_MAX); dist[src] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({ 0, src }); while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (Node neighbor : adjList[u]) { int v = neighbor.dest; int weight = neighbor.weight; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push({ dist[v], v }); } } } cout << "Shortest distances from source " << src << " to other vertices:" << endl; for (int i = 0; i < V; i++) { cout << "Vertex " << i << ": " << dist[i] << endl; } } }; int main() { Graph g(6); g.addEdge(0, 1, 5); g.addEdge(0, 2, 3); g.addEdge(1, 3, 6); g.addEdge(1, 4, 2); g.addEdge(2, 1, 1); g.addEdge(2, 4, 4); g.addEdge(3, 5, 8); g.addEdge(4, 5, 7); g.dijkstra(0); return 0; } 在这个示例中，首先创建一个Graph类来表示图，其中包括顶点数量V和邻接表adjList。addEdge函数用于添加边，dijkstra函数用于计算从源顶点到其他顶点的最短路径。
在main函数中，创建一个Graph对象并添加边，然后调用dijkstra函数计算最短路径。输出结果为从源顶点0到其他顶点的最短距离。您可以根据自己的需求修改顶点数量和边的权重来自定义图。
