dijstra模板.txt

来自「标准c++ acm算法实现,DFS求无向图生成树的算法.copy 至vc6.0 」· 文本 代码 · 共 63 行

Dijkstra单源最短路径的算法： 

模板如下： 

#include <stdio.h> 
#include <string.h> 

int nearvex[],lowcost[],table[][]; 
int path[];  //记录路径，记录直接后继 
double dis; 

void Dijkstra(int st,int end) 
{ 
        int i,j; 
        int top = -1; 
        nearvex[st] = -1; 
        dis = 0; 
        for(i=1;i<=n;i++) 
                if( i != st ) 
                { 
                        nearvex[i] = st; 
                        lowcost[i] = table[i][st]; 
                } 
        for(i=1;i<=n;i++) 
        { 
                int min = maxint; 
                int pmin; 
                for(j=1;j<=n;j++) 
                        if(nearvex[j] != -1 && lowcost[j] < min) 
                        { 
                                min = lowcost[j]; 
                                pmin = j; 
                        } 
                path[nearvex[pmin]] = pmin; 
                nearvex[pmin] = -1; 
                if(pmin == end) return ; 
                for(j=1;j<=n;j++) 
                        if(nearvex[j] != -1 && lowcost[pmin] + table[j][pmin] < lowcost[j]) 
                        { 
                                lowcost[j] = lowcost[pmin] + table[j][pmin]; 
                                nearvex[j] = pmin; 
                        } 
        } 
} 

//路径的输出 
void output(int st , int end) 
{ 
        int next = st; 
        do{ 
                printf("%d ",path[next]); 
                next = path[next]; 
        }while(next != end); 
} 

int main() 
{ 
        scanf("%d%d",&st,&end); 
        Dijkstra(st,end); 
} 

// Single -- Source Shortest Path Problem