四种算法 Dijkstra bellman spfa Floyd 模版

void Dijkstra(int v0)///求顶点到其他顶点的最短距离{    for(int i=0; i<n; i++)    {        dist[i]=Eage[v0][i];        vis[i]=0;///标记变量    }    vis[v0]=1;    dist[v0]=0;///将v0加入集合S    for(int i=0; i<n-1; i++) ///从顶点v0确定n-1条最短路径    {        int min=INF,u=v0;        for(int j=0; j<n; j++)        {            if(!vis[j]&&dist[j]<min)            {                u=j;                min=dist[j];            }        }        vis[u]=1;        for(int k=0; k<n; k++)        {            if(!vis[k]&&Eage[u][k]<INF&&dist[k]>dist[u]+Eage[u][k])            {                dist[k]=dist[u]+Eage[u][k];            }        }    }}void bellman(int v0)///求顶点v0到其他顶点的最短距离{    for(int i= 0; i<n; i++) ///初始化    {        dist[i]=Eage[v0][i];    }    for(int k=1; k<n; k++) ///递推n-1次    {        for(int u=0; u<n; u++) ///修改每个顶点的dist[u]        {            if(u!=v0)            {                for(int j=0; j<n; j++) ///找u的邻接点                {                    if(Eage[j][u]<INF&&dist[u]>dist[j]+Eage[j][u])                    {                        dist[u]=dist[j]+Eage[j][u];///更新                    }                }            }        }    }}void spfa(int v0){    for(int i=0; i<n; i++) ///初始化    {        dist[i]=INF;        vis[i]=0;///标记是否在队列里    }    queue<int >q;    while(!q.empty())q.pop();    dist[v0]=0;    vis[v0]=1;    q.push(v0);///起点入队列    while(!q.empty())    {        int u=q.front();        q.pop();        vis[u]=0;        for(int i=0; i<n; i++)        {            if(i!=u&&Eage[u][i]<INF)///邻接点            {                int v=i;                if(dist[v]<dist[u]+Eage[u][v])                {                    dist[v]=dist[u]+Eage[u][v];///更新                    if(!vis[v])///如果没在队列里                    {                        vis[v]=1;                        q.push(v);                    }                }            }        }    }}void Floyd(){    for(int i=0; i<n; i++)    {        for(int j=0; j<n; j++)        {            A[i][j]=Eage[i][j];        }    }    for(int k=0; k<n; k++)    {        for(int i=0; i<n; i++)        {            for(int j=0; j<n; j++)            {                if(k==i||k==j)continue;                if(A[i][k]+A[k][j]<A[i][j])                {                    A[i][j]=A[i][k]+A[k][j];                }            }        }    }}