对DAG的单源最短路问题的线性时间算法

2009-03-30 17:00 

#include<iostream>
#include<fstream>
using namespace std;
const int MAX = 100;
const int INFI = 100000;
#define WHITE 0
#define GRAY -1
#define BLACK 1
struct{
      int n;
      int adjvex[MAX];
      int weight[MAX];
}Edge[MAX];
int List[MAX],k;
int color[MAX];
int D[MAX],father[MAX];
void DFS(int cur){
     int i,next;
    
     color[cur] = GRAY;
     for(i=0;i<Edge[cur].n;i++){
         next = Edge[cur].adjvex[i];
        
         if(color[next]==WHITE) DFS(next);
         else if(color[next]==GRAY){//有回边出现意味着有回路

              cout<<"Circuit exists!"<<endl;
              system("pause");
              exit(0);
         }
     }
    
     color[cur] = BLACK;
     List[--k] = cur;//按节点完成的顺序入列

}
void TopologicalSort(int n){
     int i,j;
    
     k = n;
     memset(color,0,sizeof(color) );
     DFS(1);
}
void DAG_SP(int s,int n);
int main(void){
    int n,e,s,a,b,v;
    int i,j;
    ifstream in("data.in");
    ofstream out("data.out");
   
    in>>n>>e>>s;
    for(i=1;i<=n;i++)
        Edge[i].n = 0;
   
    for(i=0;i<e;i++){
        in>>a>>b>>v;
        Edge[a].adjvex[ Edge[a].n ] = b;
        Edge[a].weight[ Edge[a].n++ ] = v;
    }
   
    DAG_SP(s,n);
   
    for(i=1;i<=n;i++)
        out<<i<<" "<<D[i]<<" "<<father[i]<<endl;
   
    system("pause");
    return 0;
}
void DAG_SP(int s,int n){
     int i,j,u,v,w;
    
     TopologicalSort(n);
    
     for(i=1;i<=n;i++){
         D[i] = INFI;
         father[i] = 0;
     }
     D[s] = 0;
    
     for(i=0;i<n;i++){
         u = List[i];
         for(j=0;j<Edge[u].n;j++){
             v = Edge[u].adjvex[j];
             w = Edge[u].weight[j];
             if(D[v]>D[u]+w){
                D[v] = D[u] + w;
                father[v] = u;
             }
         }
     }
}