有向无环图的最短路径

给定一个有向无环图（DAG）和一个源点，求从该源点到其他所有的顶点的最短路径。如果是无负权（即权值为负），可以用djistra算法完成。但如果存在负权，则不行。同时，djistra算法效率并不高，既然是有向无环图（DAG），则可以利用拓扑排序的结果求出给定源点的最短路径。其时间复杂度是线性时间复杂度O（V+E）。关于拓扑排序，本文就不再给出具体说明，可以参考相关的资料。首先给出一个有向无环图及它的拓扑序列，如下图：

，其拓扑序列为r->s->t->x->y->z

求它的最短路径算法描述如下：

1.对有向无环图进行拓扑排序;

2.我们将到源点的距离初始化为0并将到其它所有顶点的距离设置为无穷大，如下图：

3.对于得到的拓扑序列，遍历一遍，对于每一个元素，看它的邻接边，（因为拓扑序列中当前元素只可能存在指向在它之后的元素的边），对它的邻接边做松弛操作，这样一遍过后，就得到了给定源节点的单源最短路径！具体如下图：

s到t的最短路径长度为2,因此修改d[t]=2,s到x的目前最短路径为6，因此修改d[x]=6,一次松弛操作完成，结果如上图所示。

继续遍历下一个顶点t,重复第3步（非常类似djistra），结果如下图

继续，t完了，x继续，结果如下图

继续x完了，下个顶点y,y完了，下个顶点z,结果如下图：

C++完整代码：（直接可用，来自互联网）

#include


#include
#include


#include
#define INF INT_MAX
using namespace std;
// 邻接表节点
class AdjListNode
{

    int v;
    int weight;
public:
    AdjListNode(int _v, int _w)  { v = _v;  weight = _w;}
    int getV()       {  return v;  }
    int getWeight()  {  return weight; }
};
// 图
class Graph
{

    int V;    // 顶点个数
    list

*adj;

    void topologicalSortRecall(int v, bool visited[], stack

&stk);

public:
    Graph(int V);
    void addEdge(int u, int v, int weight);
    void shortestPath(int s);
};
Graph::Graph(int V)
{

    this->V = V;
    adj = new list

[V];

}
void Graph::addEdge(int u, int v, int weight)
{

    AdjListNode node(v, weight);
    adj[u].push_back(node);
}
// 拓扑排序，递归调用。
void Graph::topologicalSortRecall(int v, bool visited[], stack

&stk)

{

    // 标记当前节点是访问过的
    visited[v] = true;
    list

::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)
    {

        AdjListNode node = *i;
        if (!visited[node.getV()])
            topologicalSortRecall(node.getV(), visited, stk);
    }
    stk.push(v);
}

// 从给定的源点s 找出到其它顶点的最短距离.
void Graph::shortestPath(int s)
{

    stack

stk;

    int dist[V];
    //标记所有顶点为未访问过的
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // 拓扑排序，结果存入stk中
    for (int i = 0; i < V; i++)
        if (visited[i] == false)
            topologicalSortRecall(i, visited, stk);
    // 初始化距离
    for (int i = 0; i < V; i++)
        dist[i] = INF;
    dist[s] = 0;
    // 按照拓扑排序的顺序处理 各个顶点
    while (stk.empty() == false)
    {

        // 获得拓扑排序的下一个顶点
        int u = stk.top();
        stk.pop();
        // 更新所有相邻的顶点
        list

::iterator i;

        if (dist[u] != INF)
        {

          for (i = adj[u].begin(); i != adj[u].end(); ++i)
             if (dist[i->getV()] > dist[u] + i->getWeight())
                dist[i->getV()] = dist[u] + i->getWeight();
        }
    }
    // 打印结果
    for (int i = 0; i < V; i++)
        (dist[i] == INF)? cout << "INF ": cout << dist[i] << " ";
}
// 测试
int main()
{

    Graph g(6);
    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);
    g.addEdge(4, 5, -2);
    int s = 1;
    cout << "Following are shortest distances from source " << s <<" \n";
    g.shortestPath(s);
    return 0;
}

主要参考了
参考：http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/