在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到其他頂點的最短距離。您可以根據自己的需求修改頂點數量和邊的權重來自定義圖。