dijkstra算法c++
时间: 2023-08-03 15:30:34 浏览: 50
下面是一个简单的 C++ 实现 Dijkstra 算法的示例代码:
```cpp
#include<iostream>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f; // 无穷大
int graph[100][100]; // 图的邻接矩阵
int dist[100]; // 存储最短路径
bool vis[100]; // 标记是否访问过
// Dijkstra 算法
void dijkstra(int start, int n)
{
memset(vis, false, sizeof(vis)); // 初始化
memset(dist, INF, sizeof(dist));
dist[start] = 0;
for(int i=1; i<=n; i++)
{
int k = -1;
for(int j=1; j<=n; j++)
{
if(!vis[j] && (k==-1 || dist[k]>dist[j]))
{
k = j;
}
}
vis[k] = true;
for(int j=1; j<=n; j++)
{
if(!vis[j] && graph[k][j]!=INF && dist[k]+graph[k][j]<dist[j])
{
dist[j] = dist[k]+graph[k][j];
}
}
}
}
int main()
{
int n, m; // n 个节点,m 条边
cin >> n >> m;
memset(graph, INF, sizeof(graph)); // 初始化
for(int i=1; i<=n; i++)
{
graph[i][i] = 0;
}
for(int i=1; i<=m; i++)
{
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = graph[v][u] = w;
}
int start;
cin >> start;
dijkstra(start, n);
for(int i=1; i<=n; i++)
{
if(dist[i]==INF)
{
cout << "INF" << endl;
}
else
{
cout << dist[i] << endl;
}
}
return 0;
}
```
该代码使用邻接矩阵存储图,时间复杂度为 O(n^2),其中 n 为节点个数。