首页 > 代码库 > Dijkstra算法——通过边实现松弛
Dijkstra算法——通过边实现松弛
算法思想：每次找到离源点最近的顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径.时间复杂度是O(N^2).
基本步骤：
- 将所有的顶点分为两部分，已知最短路程的顶点集合S和未知最短路径的顶点集合V. 最开始，已知最短路径在集合S中只有源点一个顶点，用book数组来标记哪些点在集合S中.
- 设置源点p到自己的最短路径为0(即dis[p] = 0). 若存在有源点能直接到达的顶点i，则把dis[i] 设为 e[p][i]. 同时把所有其他(源点不能直接到达的)顶点的最短路径设为∞.
- 在集合V的所有顶点中选择一个离源点p最近的顶点u(即dis[u]最小)加入到集合P中. 并考察所有以点u为起点的边，对每一条边进行松弛操作.
- 重复第3步，如果集合V为空，则结束，最终得到的dis数组中的值就是源点到所有顶点的最短路径.
一个点到其余各个顶点的最短路径也叫做“单源最短路径”. 这个Dijkstra同样求最短路径的图同样不能有负权边，因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路径不会改变的性质.
Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 999999
int book[10]; /// 用来纪录已经是最短路径的点
int main(int argc, char const *argv[])
{
int i, j, m, n;
int q1, q2, q3;
int u, v, min;
int e[100][100], dis[10];
scanf("%d %d", &n, &m);
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= n; ++j)
{
if(i == j)
{
e[i][j] = 0;
}
else
{
e[i][j] = INF;
}
}
}
for(i = 1; i <= m; ++i)
{
scanf("%d %d %d", &q1, &q2, &q3);
e[q1][q2] = q3;
}
for(i = 1; i <= n; ++i)
{
dis[i] = e[1][i];
}
book[1] = 1; /// Dijkstra 算法核心
for(i = 1; i < n; ++i) /// 计算n-1次
{
min = INF;
for(j = 1; j <= n; ++j)
{
if(dis[j] < min && book[j] == 0)
{
min = dis[j];
u = j;
}
}
book[u] = 1;
for(v = 1; v <= n; ++v)
{
if(e[u][v] != INF && dis[v] > dis[u] + e[u][v])
{
dis[v] = dis[u] + e[u][v]; /// 这个过程就是"松弛"
}
}
}
for(i = 1; i <= n; ++i)
{
printf("%d ", dis[i]);
}
printf("\n");
system("pause");
return 0;
}
Dijkstra算法——通过边实现松弛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。