以oj 2134题 图结构练习——最短路径为例
#include <iostream>
#include <climits>
#define INF 0x3f3f3f3f
using namespace std;
int dist[200], gra[200][200], vis[200];
int n;
void Dijkstra(int begins)
{
int i, j, k;
///初始化dist数组(记录每个顶点到源点最短路径的估计值),vis数组(记录每个顶点是否已经找到最短路径)
for(i = 1; i <= n; i++)
{
dist[i] = gra[begins][i];
vis[i] = 0;
}
vis[begins] = 1; //源点的最短路径已经找到;
dist[begins] = 0; //源点到本身的最短路径为0;
for(i = 0; i < n - 1; i++) //寻找n-1次,将除了源点外的所有顶点最短路径找到(保证图是连通的)
{
///每次找到与源点距离(即dist数组中的数值)估计值最小的点
int mins = INT_MAX;
for(j = 1; j <= n; j++) //顶点从1号到n号
{
if(mins > dist[j] && !vis[j])
{
mins = dist[j];
k = j;
}
}
vis[k] = 1; //该点的最短路径已经确定
//对与该点相连的顶点进行松弛操作
for(j = 1; j <= n; j++) //顶点从1号到n号
{
if(dist[j] > dist[k] + gra[k][j] && !vis[j]) //如果源点到j的距离大于源点到k的距离加上k点到j点的距离,就更新dist【j】
{
dist[j] = dist[k] + gra[k][j];
}
}
}
}
int main()
{
int m, a, b, c;
while(cin >> n >> m)
{
///初始化图的存储结构
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i == j)
gra[i][j] = 0; //自己到自己的距离为零
else
gra[i][j] = INF; //其他点初始化为无穷大
}
}
for(int i = 0; i < m; i++)
{
cin >> a >> b >> c;
if(gra[a][b] > c)
gra[b][a] = gra[a][b] = c;
}
Dijkstra(1);
cout << dist[n] << endl;
}
return 0;
}