Dijkstra算法

int n;
int map[100][100];//存储图的邻接矩阵有连接的为权值不连通权值为MAX

bool visited[100];//存储节点是否被访问

int path[100];//存储节点的父节点索引为子节点编号值为父节点编号

int dist[100];//存储源节点到j的距离不连通权值为MAX

int Dijkstra(int s,int t)
{
    int i,j,min,locate;
    memset(visited,false,sizeof(visited));
    for(i=0;i<n;i++)
    {
        dist[i]=map[s][i];
    }
    visited[s]=1;//设置源节点被访问

    path[s]=0;
    dist[s]=0;
    for(i=1;i<n;i++)
    {
        min=MAX， locate=s;
        for(j=0;j<n;j++)
        {
            if(!visited[j]&&(min>dist[j]))
            {
                min=dist[j];
                locate=j;
            }
        }
        visited[locate]=true;//设置locate节点被访问

        for(j=0;j<n;j++)
        {//j到s点的距离大于j到locate到s的距离

            if(!visited[j]&&map[locate][j]!=MAX&&(dist[j]>d[locate]+map[locate][j]))
            {
                dist[j]=dist[locate]+map[locate][j];
                path[j]=locate;
            }
        }
    }
    return d[t];
}