浙江财经大学
信息管理与工程学院

单源最短路(Dijkstra)

本文由 Ocrosoft 于 2016-12-19 12:18:51 发表
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 1001+10
using namespace std;
int n,m;
int Edge[MAXN][MAXN];
int S[MAXN],dist[MAXN],path[MAXN];
void Dijkstra(int v0)
{
    for(int i=1; i<=n; i++)
    {
        dist[i]=Edge[v0][i],S[i]=0;//均未选择
        if(i!=v0&&dist[i]<INF)path[i]=v0;//如果这个点能走,标记父节点为v0
        else path[i]=-1;//走不到
    }
    S[v0]=1,dist[v0]=0;//加入到集合中
    for(int i=1; i<=n-1; i++)
    {
        int minn=INF,u=v0;
        for(int j=1; j<=n; j++) //找出当前最短路径
            if(!S[j]&&dist[j]<minn)u=j,minn=dist[j];
        S[u]=1;//该顶点加入集合
        for(int j=1; j<=n; j++)//更新
            if(!S[j]&&Edge[u][j]<INF&&dist[u]+Edge[u][j]<dist[j])
                dist[j]=dist[u]+Edge[u][j],path[j]=u;
    }
}
int main()
{
    while(cin>>n>>m&&(n||m))
    {
        ms(Edge),ms(dist),ms(S),ms(path);
        for(int i=1; i<=m; i++)
        {
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            Edge[v][u]=w,Edge[u][v]=w;//无向边
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(i==j)Edge[i][j]=0;//自己走到自己距离为0
                else if(!Edge[i][j])Edge[i][j]=INF;//其他点如果数据没给出,说明走不到
            }
        }
        Dijkstra(1);
        printf("%d\n",dist[n]);
    }
    return 0;
}

欢迎分享与转载,请保留链接与出处。Ocrosoft » 单源最短路(Dijkstra)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址