Dijkstra算法是由荷兰计算机科学家Edsger Wybe Dijkstra发明的一种经典的最短路问题算法，适用于无负权边的图的单源最短路径问题。所谓单源最短路径，就是计算出从图中某一个节点到图中其他所有节点的最短路径。
该算法的大体思路如下：
- 从未访问过的成本最小的点出发（第一轮执行时从源节点出发），遍历所有相邻节点，并将当前节点标记为已访问
- 若相邻节点新计算的成本低于先前计算的成本，则将其最短路径更新为当前路径
- 重复1~2，直到所有节点都被访问
为了实现这一算法，我们需要定义一个graph[N][N]用于存储边（这里使用邻接矩阵，参见邻接矩阵与邻接链表），并使用sln[N]来存储到达每个点的最短路径，同时用status[N]来存储每个点的访问状态。
下面，我们来看一下具体的代码实现：
#include <iostream>
#include <vector>
using namespace std;
#define INFINITE 0x3f3f3f
int graph[1001][1001];
int sln[1001];
int main()
{
int n, m, x; //n-点数，m-边数，x-起点
cin >> n >> m >> x;
for (int i = 0; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j)
graph[i][j] = 0;
else
graph[i][j] = INFINITE;
}
sln[i] = INFINITE;
}
graph[0][0] = INFINITE;
for (int i = 1; i <= m; i++)
{
int a, b, t; //a-边起点，b-边终点，t-边权值
cin >> a >> b >> t;
graph[a][b] = t;
}
int chosen = x;
vector<bool> status(n + 1, true);
status[x] = false;
sln[x] = 0;
for (int i = 1; i < n; i++)
{
int selected = 0;
for (int j = 1; j <= n; j++)
{
if (sln[j] > sln[chosen] + graph[chosen][j])
sln[j] = sln[chosen] + graph[chosen][j];
if (status[j] && sln[selected] > sln[j])
selected = j;
}
status[selected] = false;
chosen = selected;
}
for (int i = 1; i <= n; i++)
{
cout << sln[i] << " ";
}
return 0;
}
在以上代码中，我们将INFINITE定义为0x3f3f3f3f，防止在计算新成本时溢出。
以上就是Dijkstra的原始算法，其时间复杂度为\(O(V^2)\)。当然，Dijkstra算法还有许多优化版本，就留待读者自行探索。
发表回复