最短路径(Dijkstra)-HDU 2544-最短路

亦凉 2022-05-14 03:38 296阅读 0赞

  • 最短路径(Dijkstra)-HDU 2544-最短路

  • 题目链接：

最短路

  • 题目基础：

最短路径-Dijkstra(迪杰斯特拉)算法

  • 思路：

题目大意：

略略略~~

题解：

套模板，传送门有详解

  • 代码：

    include

    include

    using namespace std;

    define MAX_SIZE 1024

    define INF 65535

    //邻接图
    struct MGrapth
    {

    1. int Vexs[MAX_SIZE];  //顶点表
    2. int Arc[MAX_SIZE][MAX_SIZE];  //邻接矩阵
    3. int Num_Vertext,Num_Edges;  //顶点数，边数

    };
    MGrapth Map;

    int Path[MAX_SIZE]; /表示路径 Path[i]->i/
    int Short_Path[MAX_SIZE]; /Start->i 的最短路径和/
    bool Vis[MAX_SIZE]; /当前最短路径结点true/

    void Init(int n,int m)
    {

    1. Res=0;
    2. memset(Vis,0,sizeof(Vis));
    3. memset(Path,0,sizeof(Path));
    4. for(int i=0;i<=n;i++)
    5.     for(int j=0;j<=m;j++)
    6.         Map.Arc[i][j]=INF;
    7. Map.Num_Vertext=n;
    8. Map.Num_Edges=m;

    }

    void Dijkstra(int Start)
    {

    1. int v,w,k,Min;
    2. for(v=0;v<Map.Num_Vertext;v++)
    3.     Short_Path[v]=Map.Arc[Start][v];  /*Start到相连结点的距离*/
    5. Short_Path[Start]=0;   /*Start->Start 的距离为0*/
    6. Vis[Start]=1;   /*Start为当前最短路径结点*/
    8. for(v=1;v<Map.Num_Vertext;v++)
    9. {
    10.     Min=INF;
    11.     for(w=0;w<Map.Num_Vertext;w++)
    12.     {
    13.         if(!Vis[w]&&Short_Path[w]<Min)
    14.         {
    15.             k=w;
    16.             Min=Short_Path[w];
    17.         }
    18.     }
    19.     Vis[k]=true; /*找出最短路到散点的最小值，将该散点连入最短路*/
    21.     for(w=0;w<Map.Num_Vertext;w++)  /*更新最短路*/
    22.     {
    23.         if(!Vis[w]&&Min+Map.Arc[k][w]<Short_Path[w])  /*图中某点到v0的距离比当前路短，更新*/
    24.         {
    25.             Short_Path[w]=Min+Map.Arc[k][w];
    26.             Path[w]=k;
    27.         }
    28.     }
    29. }

    }

    int main()
    {

    1. int M,N;
    2. int A,B,C;
    3. while(cin>>N>>M)
    4. {
    5.     if(N==0&&M==0)
    6.         break;
    7.     Init(N,M);
    8.     for(int i=0;i<M;i++)
    9.     {
    10.         cin>>A>>B>>C;
    11.         if(Map.Arc[A-1][B-1]>C)   //最小坐标当成0来写
    12.             Map.Arc[A-1][B-1]=C;
    13.         if(Map.Arc[B-1][A-1]>C)
    14.             Map.Arc[B-1][A-1]=C;
    15.     }
    16.     Dijkstra(0);
    17.     cout<<Short_Path[N-1]<<endl;

    }
    return 0;
    }

发表评论

表情：
评论列表 （有 0 条评论，296人围观）

还没有评论，来说两句吧...

相关阅读

    相关 最短路径

    最短路径的迪杰斯特拉算法跟最小生成树的普利姆算法很像！   但是这里的像只是代码相似，实质是不一样的！   普利姆算法是从任意点开始，找到跟他最近的点记录距离，然后

    比眉伴天荒比眉伴天荒/ 0 赞/ 266 阅读