最短路径----Dijstra

单源最短路径

思路:

寻找一个确定离起点最近的点，并给他打上标记，再用这个点当为中间点去更新其余的点。
用vis标记i点是否为已经确定的点
用dis存放起点到每i点的最短距离

时间复杂度O(n²)

Code:

#include<iostream>
#include<cmath>
#include<memory.h>
using namespace std;
int vis[1000];//判断i点是否已经是最短
int dis[1000];//起点其余每个点的距离
int map[1000][1000];//邻接矩阵
int n,m,s;//顶点数，边数，起点
dijstra(int s)
{
    memset(vis,0,sizeof(vis));//将每个点都设为未走过
    memset(dis,ox3f,sizeof(dis));//起点到每个点的初值都为正无穷
    for(int t=1;t<=n;t++)//n个点，所以循环n次
    {
        int minz=0x7f,mini=0;//minz为最小值，mini为最小值的下标
        for(int i=1;i<=n;i++)//遍历每个点
        {
            if(vis[i]==0&&minz>dis[i])//寻找起点到为访问过点的最小值
            {
                mini=i;//最小值的下标
                minz=dis[i];//最小值
            }
         } 
         vis[mini]=1;//给最小值的下标打个标记
         for(int i=1;i<=n;i++)
         dis[i]=min(dis[i],dis[mini]+map[mini][i]);//更新起点到其余个点的距离
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        map[u][v]=map[v][u]=w;
    }
    dijstra(s);
    for(int i=1;i<=n;i++)
    cout<<dis[i]<<" ";//输出起点到各个点的距离
    return 0;
}