最短路径DIJ

本文主要是介绍最短路径DIJ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

   N//有N个连线

   X，y,v//序号X和序号Y之前的路费为V。

   。。。。。。。。

   X　Y／／只有一行要求输出序号X到序号Y的最短路。

程序：

  

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

using namespace std;
int n,m,i,j,minn,k,x,y,v,a[1001][1001]={1001},f[1001],dis[1001];
int main()
{
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
        cin>>x>>y>>v;
        a[x][y]=v;
        a[y][x]=v;
    }
    cin>>x>>y;
    for (i=1;i<=n;i++)
    {
        dis[i]=a[x][i];
    } 
    
    f[x]=1;
    dis[x]=0;
    for (i=1;i<=n;i++)
    {
        minn=10000;
        for (j=1;j<=n;j++)
          {
              if (f[j]==0&&dis[j]<minn) 
              {
                  k=j;
                  minn=dis[j];                  
              }
          }
        f[k]=1;
        if (k==y) break;
        for (j=1;j<=n;j++)
        {
            if (f[j]==0&&dis[k]+a[k][j]<dis[j]) dis[j]=dis[k]+a[k][j];          
            
        }
    }
  cout<<dis[y];

  return 0;
}

　　

   

这篇关于最短路径DIJ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---