dijkstra的两种写法

第一种，先处理源点的邻接结点，再循环处理其他结点（同陈越姥姥慕课代码）

int findMin(){//查找为收录结点中dist最小的点
    int mind=inf;
    int minv=-1;
    for(int i=1;i<=N;i++){
        if(collected[i]==false&&dist[i]<mind){
            mind=dist[i];
            minv=i;
        }
    }
    return minv;
}
void dijkstra(int P){
    int v;
    for(int i=1;i<=N;i++){//先处理源点的邻接点
        dist[i]=G[P][i];
        if(dist[i]<inf){
            path[i]=P;
        }else{
            path[i]=-1;
        }
    }
    collected[P]=true;
    while(1){//再处理其他结点
        v=findMin();
        if(v==-1){
            return ;
        }
        collected[v]=true;
        for(int i=1;i<=N;i++){
            if(collected[i]==false){
                if(dist[v]+G[v][i]<dist[i]){
                    dist[i]=dist[v]+G[v][i];
                    path[i]=v;
                    }
                }
            }
        }
    }

}

第二种，只处理源点的dist，然后把所有结点一块循环处理

void dijkstra(int v){
    int u;
    dist[v]=0;//只处理源点的dist
    for(int i=0;i<=N;i++){//把所有点一块处理
        int mind=inf;
        int minv=-1;
        for(int j=0;j<=N;j++){
            if(collected[j]==false&&dist[j]<mind){
                mind=dist[j];
                minv=j;
            }
        }
        u=minv;
        if(u==-1){
            break;
        }
        collected[u]=true;
        for(int i=0;i<=N;i++){
            if(collected[i]==false&&G[u][i]!=inf){
                if(dist[u]+G[u][i]<dist[i]){
                    dist[i]=dist[u]+G[u][i];
                    path[i]=u;
                }
            }
        }
    }
}

或许还有第三种，待更新。。。