题目描述

Dijksrtra求最短路
（最短路径算法）：从1号点（已经确定的）到目的点的最短路径

有向图

朴素版：
（1）初始化距离：dist[1]=0(1号点（第一个点）到起点的距离时0)其他的点定义为无穷
（2）

for i:1~n      迭代n次，更新n次，确保所有的点都被选完了，则时间复杂度为O(n^2)
{
    1、t  //(找到不在s中的距离最近的点)
    2、s<-t   //将点t加入到s中，按最短路径长度递增的顺序逐个将点加入到s[N]中去
    3、   //t来更新所有点的距离,则t变为中间点（从t出来的所有的边能不能更新所有点的距离即要与从源点直接到目的点的距离比较）即：判断dist[t]+w是否<dist[x]；
}

第一次迭代遍历所有点，确定他们到起点的距离
接下来的迭代从上一次算好的点中找到一个最小值，然后将他加入s，再用该点更新到其他点的距离（如果更小的话）

s[N]包含已确定最短路径的顶点，初始时只含有一个源点
t：从尚未确定最短路径的顶点中选择

稠密图：邻接矩阵
稀疏矩阵：邻接表

无向边：连两次

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=510;

int n,m;
int g[N][N];    //邻接矩阵
int dist[N];   //每个点到1号点的距离
bool st[N];  //每个点的最短路是否被确定了

int dijstra()
{
    memset(dist,0x3f,sizeof(dist));

    dist[1]=0;               //第一步，从第一个点开始

    for(int i=0;i<n;i++)    //迭代n次
    {
        //1、选一个不在s中的点
        int t=-1;

        //2、将选中的点加入s中
        for(int j=1;j<=n;j++)   //遍历所有点
        {
            //当前点还没有确定最短路（t==-1），直接赋值，或者当前点的距离不是最短的，就赋值成最短的j
            if(!st[j]&&(t==-1||dist[t]>dist[j]))   
            {
                t=j;  //就更新成j
            }
        }
        st[t]=true;//标记该点已经加入到s中，被选过了

        //3、更新距离
        for(int j=1;j<=n;j++)    //更新n次
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);   //用1到t的距离加t到这个点的距离来更新
        }
    }

    //如果最后一个点到1的距离为正无穷，则表明是不连通的，不连通就不能求最短路
    if(dist[n]==0x3f3f3f3f) return -1;    
    return dist[n];  //否则返回距离
}
int main()
{
    cin>>n>>m;
   memset(g,0x3f,sizeof g);

   while(m--)
   {
       int a,b,c;
       cin>>a>>b>>c;
       g[a][b]=min(g[a][b],c);   //a和b中可能有多条边（重边），只需要保留最短的边
   }
    //上面给临界矩阵赋值，然后用算法
   int t=dijstra();
   cout<<t<<endl;
   return 0;
}