dijkstra算法理解+模板
2017-09-17 21:10:45
writer：pprp
看了看dijkstra算法，用自己语言总结一下主要过程吧，
首先，明确这个算法用处是在于计算单源最短路径问题并且边权非负，给出一个起点可以找到其他点的最短路径
复杂度为O(n^2)
思想：贪心的做法，每次只看现在的最短路的部分，但是要记得更新已确定该点到其他点的距离
总结一下，dijkstra的做法：
需要 dis vis map 三个数组
给出起点就可以找到到其他所有点的最短路
1、初始化dis数组和起点的dis和vis
2、进行N个点的N次循环
3、从起点开始，找到距离最短的点
4、然后将其dis和vis更改,
5、更改该点相连的其他点的距离
模板如下：
const int maxn = 1010;
const int INF = 0x3f3f3f3f;
int mp[maxn][maxn];
bool vis[maxn];
int dis[maxn];
void Dijkstra(int st)
{
for(int i = 1 ; i <= N; i++)//更新dis数组
{
dis[i] = mp[st][i];
}
vis[st] = 1;
dis[st] = 0;
int rec = -1;
for(int i = 1 ; i < N ; i++)//起到了循环的作用
{
Min = INF;
rec = -1;
for(int j = 1; j <= N; j++)//找到当前的可以到达的最短距离的点
{
if(!vis[j] && Min > dis[j])
{
rec = j;
Min = dis[j];
}
}
if(rec == -1)return ;
vis[rec] = 1;
for(int j = 1; j <= N; j++)//更新该点连接到的其他的点
{
if(!vis[j] && mp[rec][j] != INF && dis[rec] + mp[rec][j] < dis[j])
dis[j] = mp[rec][j] + dis[rec];
}
}
}使用方法：
for(int i = 0 ; i < maxn; i++)
for(int j = 0 ; j < maxn; j++)
mp[i][j] = INF;
memset(vis,0,sizeof(vis));
for(int i = 0 ; i < T ; i++)
{
cin >> x >> y >> v;
if(v < mp[x][y])//去重
mp[x][y] = mp[y][x] = v;
}
Dijkstra(N);
for(int i = 1; i < N ; i++)
cout << dis[i] << " ";
cout << endl;
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。