当图中没有环时，使用Bellman-Ford这一低效算法显然就不划算了，这时我们可以选择DAG算法。

    本文使用C++实现了这一基本算法。参考《算法导论》第24.2节

    笔者使用了vector实现邻接链表，以提高运行效率。 

/** * DAG's Single Source Shortest Path Algorithm in C++ * Based on DFS, don't let any circle exist in the graph * Time Cost : O(|N|+|M|) * Introduction to Algorithms (CLRS) 24.2 * Author: Zheng Chen / Arclabs001 * Copyright 2015 Xi'an University of Posts & Telecommunications */#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define INF 0xfffffffusing namespace std;const int N = 6;const int M = 10;ifstream in;enum status {UNDISCOVERED,DISCOVERED,VISITED};struct edge{    int dest;    int weight;};struct vertex{    int num;    int dist;    int inDegree,outDegree;    status _stat;    vertex * parent;}V[N];vector
        
          AdjList[N];stack
         
           vertexStack;   //The call srackstack
          
            topo_order;int t;void initialize(int s){    for(int i=0; i
           
            
             >_start>>_dest>>_weight;        tmp->dest = _dest;        tmp->weight = _weight;        V[_start].outDegree++;        V[_dest].inDegree++;        AdjList[_start].push_back(*tmp);    }    V[s].dist = 0;    t = 0;}void relax(int u, int v, int weight)  //The "relax" operation{    if(V[v].dist > V[u].dist + weight)    {        V[v].dist = V[u].dist + weight;        V[v].parent = &V[u];    }}/** * The main dfs-visit function, to get the topo-order of the graph * @param i [the root of each tree] */void dfs_Visit(int i){    V[i]._stat = DISCOVERED;    edge tmp;    for(int j=0; j
             
              
               num;    else if(v->parent == nullptr)        cout<<"No path from "<
               
                num<<" to "<
                
                 num<
                 
                  parent);        cout<<"->"<
                  
                   num;    }}int main(){    in.open("DAG.txt");    int s = 1;    DAG_shortest_path(s);    cout<<"Succeed ! The distance of each vertex are :"<
                   
                    
                     <<"INF "; else cout<
                     
                      <<" ";    cout<
                      
                       <<"One of the shortest path is :"<
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

//DAG.txt文件内容如下：

0 1 5

0 2 3

1 2 2

1 3 6

2 3 7

2 4 4

2 5 2

3 4 -1

3 5 1

4 5 -2

每一行的三个元素分别表示某条边的起始节点、终止节点、这条边的权重。