給定一個有向無環圖和源點s,并求s到其它各頂點的最短路徑,在圖中無負邊時,通常采用Dijkstra算法（O(V^2)）; 有負邊是則采用Bellman-Ford算法(O(VE));均無法在線性時間內得到結果,而如果先對鄰接表結構的有向圖采用拓撲排序,得到排序后的數組PRint，然后從源點開始更新鄰接結點的最小路徑,最終可得到源點到其它所有結點的最短路徑

關于拓撲排序，核心是先將所有入度為0的結點入棧,然后依次出棧(用print數組保存),同時將鄰接結點入度減1(減為0時要入棧)

下面這張圖很好地顯示了具體的流程：

下面的C代碼采用的是上面的算法

#include <stdio.h>#include <stdlib.h>#include <string.h> #define MaxSize 1000#define TRUE 1#define FALSE 0 #define INF 0x3f3f3f3f//1061109567 //typedef int VertexType;//邊表結點typedef struct arcnode{	int adjvex; //鄰接點域,存儲頂點對應的下標 	int weight; 	struct arcnode *nextarc; //鄰域,指向下一個鄰接點 }ArcNode;//頂點表typedef struct{//	VertexType data;	ArcNode *firstarc; //邊表頭結點 }VNode; //鄰接表定義typedef struct{	VNode adjlist[MaxSize];	int n,e;}AGraph;//順序棧typedef struct{	int top;	int data[MaxSize];}SqStack;int indegree[MaxSize],print[MaxSize],min_dis[MaxSize];//print為拓撲排序后的結果 void InitStack(SqStack *S){      S->top = -1;   }  void Push(SqStack *S,int i){      S->data[++(S->top)] = i;  }  void Pop(SqStack *S,int *i){      *i = S->data[S->top--];  }  int IsEmpty(SqStack S){      if(S.top == -1)          return TRUE;      else{          return FALSE;      }  } void CreateGraph(AGraph *G){	int tail,head,w;	for( int i = 0 ; i < G->n ; i ++ ) //初始化頂點表指針 		G->adjlist[i].firstarc = NULL;	for( int i = 0 ; i < G->e ; i ++ ){		scanf("%d%d%d",&tail,&head,&w);		indegree[head] ++;		//頭插法 		ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));		p->nextarc = G->adjlist[tail].firstarc;		G->adjlist[tail].firstarc = p;//		p->adjvex = head;		p->weight = w;	}}void TopologicalSort(AGraph G){	SqStack S; //用棧或隊列都可以	InitStack(&S);	for( int i = 0 ; i < G.n ; i ++ )		if(!indegree[i])			Push(&S,i);	int count = 0;	while(!IsEmpty(S)){		int index;		Pop(&S,&index);		print[count ++] = index;		for(ArcNode *p = G.adjlist[index].firstarc ; p ; p = p->nextarc){			if(!(-- indegree[p->adjvex]))				Push(&S,p->adjvex);		}	}}void ShortestPath(AGraph G,int s){	int index;	for(int i = 0 ; i < G.n ; i ++ )		if(print[i] == s){			index = i;			break;		}	//更新最小路徑長度(如果要記載具體路徑,記住前驅結點即可,初始化均為源點) 	int s1;	for(int i = index ; i < G.n ; i ++ ){//源點前面的結點到源點距離固定為INF		s1 = print[i] ;		for(ArcNode *p = G.adjlist[s1].firstarc ; p ; p = p->nextarc){			if(min_dis[p->adjvex] > min_dis[s1] + p->weight)				min_dis[p->adjvex] = min_dis[s1] + p->weight;		}	}	//ShowPathLen	for( int i = 0 ; i < G.n ; i ++ ){		printf("%d->%d:",s,print[i]);		if(min_dis[i] == INF)			printf("INF/n");		else printf("%d/n",min_dis[i]);	}}int main(){	AGraph G;	while(~scanf("%d%d",&G.n,&G.e)){		memset(indegree,0,sizeof(indegree));		CreateGraph(&G);		TopologicalSort(G);		int s;		scanf("%d",&s);		memset(min_dis,INF,sizeof(min_dis[0])*(G.n));		min_dis[s] = 0;		ShortestPath(G,s);	}	return 0;}
下面的C++代碼參照的是最下面的網址上的代碼
#include <iostream>#include <list>#include <cstring>#include <stack>const int INF = INT_MAX;using namespace std;//鄰接表結點 class AdjacentListNode{	int v;	int w;public:	AdjacentListNode(int _v,int _w){ //帶參構造函數		v = _v , w = _w ;	}	int GetNode() { return v; }	int GetWeight() { return w; }};//圖 class Graph{	int V; 	list<AdjacentListNode> *adj;	void TopologicalSort(int v, bool visited[], stack<int> &stk); // public:	Graph(int V); //構造函數一般public 	void AddEdge(int u, int v, int w);	void ShortestPath(int s);};Graph::Graph(int V){ //構造函數不返回任何值 	this->V = V;	adj = new list<AdjacentListNode>[V]; //V個邊表結點指針 }void Graph::AddEdge(int u, int v, int w){	AdjacentListNode node(v,w); //實類化對象 	adj[u].push_back(node);}void Graph::TopologicalSort(int v, bool visited[], stack<int> &stk){  	visited[v] = true;	for(list<AdjacentListNode>:: iterator i = adj[v].begin() ; i != adj[v].end() ; i ++ ) {		if(!visited[i->GetNode()])			TopologicalSort(i->GetNode(),visited,stk);	}	stk.push(v);//圖的后繼結點 必后入棧 }void Graph::ShortestPath(int s){	stack<int> stk;	int min_dis[V]; //不需要動態開辟	bool visited[V];	memset(visited,false,sizeof(visited));//	memset(min_dis,INF,sizeof(min_dis)); //-1	for(int i = 0 ; i  < V ; i ++ )		min_dis[i] = INF;	min_dis[s] = 0;	//拓撲排序 	for(int i = 0; i < V ; i ++ )		if(!visited[i])			TopologicalSort(i,visited,stk);	//求最短路徑	while(!stk.empty()) {		int u = stk.top();		stk.pop();		//更新所有相鄰的結點		list<AdjacentListNode>:: iterator i; //迭代器(指針作用) 		if(min_dis[u] != INF){ //0之前為INF的都自動略過 			for(i = adj[u].begin(); i != adj[u].end() ; i ++ ){				if(min_dis[i->GetNode()] > min_dis[u] + i->GetWeight())						min_dis[i->GetNode()] = min_dis[u] + i->GetWeight();			}				}	}	for(int i = 0 ; i < V ; i ++ )		(min_dis[i] == INF) ? cout << "INF " : cout << min_dis[i] << " ";} int main(){	Graph g(6); 	g.AddEdge(4,5,-2);	g.AddEdge(0,1,5);	g.AddEdge(0,2,3);	g.AddEdge(1,3,6);	g.AddEdge(1,2,2);	g.AddEdge(2,4,4);	g.AddEdge(2,5,2);	g.AddEdge(2,3,7);	g.AddEdge(3,4,-1);	int s = 1;	cout << "Following are the shortest distances from source:" << endl;	g.ShortestPath(s);	return 0;}
測試樣例:
6 9
4 5 -2
0 1 5
0 2 3
1 3 6
1 2 2
2 4 4
2 5 2
2 3 7
3 4 -1
1
6 9
0 1 5
1 2 2
4 5 -2
0 2 3
2 5 2
1 3 6
2 4 4
2 3 7
3 4 -1
3
參考資料:
      http://www.acmerblog.com/shortest-path-for-directed-acyclic-graphs-5891.html