用C++做单源最短路径---dijkstra算法的全部代码
时间: 2024-03-02 17:50:22 浏览: 15
好的,下面是完整的代码,包括输入图的邻接矩阵和输出源点到其他节点的最短距离:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int n; // 图的节点数
int dis[MAXN]; // 存储源点到各个节点的最短距离
bool vis[MAXN]; // 标记节点是否已经访问过
int G[MAXN][MAXN]; // 图的邻接矩阵表示
void dijkstra(int s)
{
memset(vis, false, sizeof(vis));
memset(dis, INF, sizeof(dis));
dis[s] = 0;
for (int i = 1; i <= n; i++)
{
int k = -1;
for (int j = 1; j <= n; j++)
if (!vis[j] && (k == -1 || dis[j] < dis[k]))
k = j;
vis[k] = true;
for (int j = 1; j <= n; j++)
if (!vis[j] && dis[k] + G[k][j] < dis[j])
dis[j] = dis[k] + G[k][j];
}
}
int main()
{
// 输入图的邻接矩阵
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> G[i][j];
// 求解源点到各个节点的最短距离
int s;
cin >> s; // 输入源点
dijkstra(s);
// 输出结果
for (int i = 1; i <= n; i++)
cout << "源点" << s << "到节点" << i << "的最短距离为:" << dis[i] << endl;
return 0;
}
```
在这个代码中,我们首先输入图的邻接矩阵,然后输入源点s,调用dijkstra函数求解源点到各个节点的最短距离,最后输出结果。