C++的迪杰斯特拉
博客专区 > 侯禹 的博客 > 博客详情
C++的迪杰斯特拉
侯禹 发表于4年前
C++的迪杰斯特拉
  • 发表于 4年前
  • 阅读 109
  • 收藏 3
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

/*    Dijkstra(不存在负环回路的情况下)     */
#include <iostream>
#include <cstdio>
#include <cstring>
#define Inf 0x7fffffff
#define MaxV 10000
using namespace std;
int N,M;
int map[MaxV][MaxV];
int dist[MaxV];     //记录当前节点最短路径
int path[MaxV];     //记录最短路径前一节点
bool p[MaxV];
void dijkstra(int s)
{
    int i,j,k;
    int min;
    for(i=0;i<=N;i++)             //初始化非源点信息
    {
        p[i]=false,dist[i]=map[s][i],path[i]=s;
    }
    dist[s]=0,path[s]=s,p[s]=true;   //源点信息
    for(i=1;i<=N;i++)
    { 
        min=Inf;
        k=0;
        for(j=1;j<=N;j++)
        {
            if(!p[j]&&dist[j]<min)
            {
                min=dist[j];
                k=j;
            }
        }
        if(k == 0) {printf("buzhogn \n"); return;}
        p[k]=true;
        for(j=1;j<=N;j++)
        {
            if(!p[j]&&map[k][j]!=Inf&&dist[j]>dist[k]+map[k][j])
            {
                dist[j]=dist[k]+map[k][j];
                path[j]=k;
            }
        }
    }
}
void init()
{
    int from,to,w;
    scanf("%d%d",&N,&M);
    for(int i=0;i<=N;i++)
    for(int j=0;j<=N;j++)
    {
        if(i==j)    map[i][j]=0;
        else        map[i][j]=Inf;
    }
    for(int i=0;i<M;i++)
    {
        scanf("%d%d%d",&from,&to,&w);
        map[from][to]=map[to][from]=w;
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    init();
    dijkstra(1);
    for(int i=1;i<=N;i++)
    printf("dist[%d]   =   %d\n",i,dist[i]);
    return 0;
}


共有 人打赏支持
粉丝 94
博文 49
码字总数 34362
×
侯禹
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: