最短路径-迪杰斯特拉算法

算法模板

const int edge=7;             //edge为边长
const int INF=100000000;  //无穷大，表示两点之间无路径

void Dijkstra(int g[edge][edge],int v,int dist[],int path[]){  //dist存储最短路径  path表示最短路径的上一点
    int set[edge];   //记录数组  
    int min,i,j,u;
    
    for(i=0;i<edge;i++){  // 初始化
        dist[i]=g[v][i];
        set[i]=0;
        if(g[v][i]<INF)
            path[i]=v;
        else
            path[i]=-1;
    }
    
    set[v]=1;path[v]=-1;
    
    for(i=0;i<edge-1;i++){   // 开始寻找最短路径 时间复杂度O(n²)
        min=INF;
        for(j=0;j<edge;j++){
            if(set[j]==0&&dist[j]<min){
                u=j;
                min=dist[j];
            }
        }
        
        set[u]=1;
        for(j=0;j<edge;j++){
            if(set[j]==0&&dist[u]+g[u][j]<dist[j]){
                dist[j]=dist[u]+g[u][j];
                path[j]=u;
            }
        }
    }   
}

输出最短路径依次经过的点需要借助栈，最短路径保存在dist[]中，直接取就行了

const int maxSize=100000;
void printPath(int path[],int a){
    int stack[maxSize],top=-1;  //借助栈
    while(path[a]!=-1){
        stack[++top]=a;
        a=path[a];
    }
    stack[++top]=a;
    
    while(top!=-1)
        cout << stack[top--] << " "; 
}