2017-07-26 22:30:45
writer:pprp
dijkstra算法法则:设置顶点集合S,首先将起始点加入该集合,然后根据起始点到其他顶点的路径长度,
选择路径长度最小的顶点加入到集合S,根据所加入顶点更新源点到其他顶点的路径长度,然后再选取最小边的顶点;
实现:用邻接矩阵
适用条件:图中任意一个边都是正的
我的理解:从某一点出发,找到与该点临近有路径的点,找到其中最短路径的点,将其标记,表示已经访问过了,
然后更新距离的数组(如果通过两步路径和要比一步的路要短),还需要在深刻理解一下;
代码如下:
#include <iostream>using namespace std;const int INF = ;
int n;
int map[][]; //储存图
int visit[] = {0}; //设置访问标记
int d[]; //源点到各节点的最小距离void init()
{
cin >> n;
for(int i = ; i <= n ; i++)
for(int j = ; j <= n ; j++)
{
cin >> map[i][j];
if(map[i][j] == )
map[i][j] = INF;
}
}void Dijkstra(int x) //从x点开始到其他源点的距离
{
int i,j,Min,p;
for(i =; i<=n; i++)
d[i] = map[x][i]; //初始化最小距离
visit[x] = ; //标记为已访问过
d[x] = ; //自身到自身为0
for(i = ; i < n; i++)
{
Min = INF; //找最小边
for(j = ; j<=n; j++) //找出总和最短路径
{
if(!visit[j]&&Min>d[j])
{
p = j;
Min = d[j];
}
}
visit[p] = ;
for(j = ; j <= n; j++)
{
if(!visit[j]&&Min+map[p][j]<d[j])
d[j] = Min+map[p][j];
}
}
for(i = ;i <= n ;i++)
cout <<d[i]<<" ";
cout << endl;
}int main()
{
init();
Dijkstra();
return ;
}