2014
07-02

# 有向无环图的最短路径

-首先，我们必须对有向无环图进行拓扑排序;

-其次，我们将到源点的距离初始化为0并将到其它所有顶点的距离设置为无穷大;

-最后，对于列表中的每一个顶点，我们从它的所有邻节点中找到最短路径的那个顶点;

1) Initialize dist[] = {INF, INF, ….} and dist[s] = 0 where s is the source vertex.
2) Create a toplogical order of all vertices.
3) Do following for every vertex u in topological order.
………..Do following for every adjacent vertex v of u
………………if (dist[v] > dist[u] + weight(u, v))
………………………dist[v] = dist[u] + weight(u, v)

C++代码实现如下：

#include<iostream>
#include <list>
#include <stack>
#include <limits.h>
#define INF INT_MAX
using namespace std;

// 邻接表节点
{
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;    // 顶点个数

void topologicalSortRecall(int v, bool visited[], stack<int> &stk);
public:
Graph(int V);

void addEdge(int u, int v, int weight);

void shortestPath(int s);
};

Graph::Graph(int V)
{
this->V = V;
}

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

// 拓扑排序，递归调用。详细解释参考这里：
void Graph::topologicalSortRecall(int v, bool visited[], stack<int> &stk)
{
// 标记当前节点是访问过的
visited[v] = true;

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<int> 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();

// 更新所有相邻的顶点
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);
int s = 1;
cout << "Following are shortest distances from source " << s <<" \n";
g.shortestPath(s);

return 0;
}

1. Gucci New Fall Arrivals

This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

2. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！

3. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

4. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

5. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks