首页 > 代码库 > 迪杰斯特拉

迪杰斯特拉

const int maxn=10000+5;const int INF=1e9;int mat[maxn][maxn];int visit[maxn],dis[maxn];int n;int dijkstra(int a,int b)    //a到b的最短路径{    memset(visit,0,sizeof(visit));    for(int i = 1; i <= n; i++)        dis[i] = mat[a][i];       //最初的源点赋值    visit[a] =  true;    for(int i = 1; i <= n; i++)    {        int Min = INF;        int pos;        for(int j = 1; j <= n; j++) //找的最近的点当中转点            if(Min > dis[j] && visit[j] == 0)            {                Min = dis[j];                pos = j;            }        visit[pos] = true;          //避免重复访问        for(int j = 1; j <= n; j++)            if(dis[j] > dis[pos] + mat[pos][j] && visit[j] == 0)  //松弛                dis[j] = dis[pos] + mat[pos][j];    }    return dis[b];}

  

迪杰斯特拉