最路径问题 Shortest Path
一个节点到另一个节点最短的路径。路径规划问题。
- 路径规划
- 工作任务规划
对于无权图进行广度优先遍历就是求出了一个最短路径。
最短路径树
从起始点到其他节点路径最短的树
无权图的最短路径。
无权
有权最短路径
松弛操作。找到更短路径。
dijkstra 单源最短路径算法
前提：图中不能有负权边
复杂度 O( E log(V) )同最小生成树
最小索引堆
最短路径
从源点能到达的点中最短的路径。
图中不能有负权边
松弛操作
经过2到达1和经过2到达3比原来记录的值小，所以松弛更新。
经过1到4更短
经过1到4更短
最短
IndexMinHeap
代码实现：
// Dijkstra算法求最短路径
template<typename Graph, typename Weight>
class Dijkstra{
private:
Graph &G; // 图的引用
int s; // 起始点
Weight *distTo; // distTo[i]存储从起始点s到i的最短路径长度
bool *marked; // 标记数组, 在算法运行过程中标记节点i是否被访问
vector<Edge<Weight>*> from; // from[i]记录最短路径中, 到达i点的边是哪一条
// 可以用来恢复整个最短路径
public:
// 构造函数, 使用Dijkstra算法求最短路径
Dijkstra(Graph &graph, int s):G(graph){
// 算法初始化
assert( s >= 0 && s < G.V() );
this->s = s;
distTo = new Weight[G.V()];
marked = new bool[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
distTo[i] = Weight();
marked[i] = false;
from.push_back(NULL);
}
// 使用索引堆记录当前找到的到达每个顶点的最短距离
IndexMinHeap<Weight> ipq(G.V());
// 对于其实点s进行初始化
distTo[s] = Weight();
from[s] = new Edge<Weight>(s, s, 0);
ipq.insert(s, distTo[s] );
marked[s] = true;
while( !ipq.isEmpty() ){
int v = ipq.extractMinIndex();
// distTo[v]就是s到v的最短距离
marked[v] = true;
// 对v的所有相邻节点进行更新
typename Graph::adjIterator adj(G, v);
for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ){
int w = e->other(v);
// 如果从s点到w点的最短路径还没有找到
if( !marked[w] ){
// 如果w点以前没有访问过,
// 或者访问过, 但是通过当前的v点到w点距离更短, 则进行更新
if( from[w] == NULL || distTo[v] + e->wt() < distTo[w] ){
distTo[w] = distTo[v] + e->wt();
from[w] = e;
if( ipq.contain(w) )
ipq.change(w, distTo[w] );
else
ipq.insert(w, distTo[w] );
}
}
}
}
}
// 析构函数
~Dijkstra(){
delete[] distTo;
delete[] marked;
delete from[0];
}
// 返回从s点到w点的最短路径长度
Weight shortestPathTo( int w ){
assert( w >= 0 && w < G.V() );
assert( hasPathTo(w) );
return distTo[w];
}
// 判断从s点到w点是否联通
bool hasPathTo( int w ){
assert( w >= 0 && w < G.V() );
return marked[w];
}
// 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
void shortestPath( int w, vector<Edge<Weight>> &vec ){
assert( w >= 0 && w < G.V() );
assert( hasPathTo(w) );
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
stack<Edge<Weight>*> s;
Edge<Weight> *e = from[w];
while( e->v() != this->s ){
s.push(e);
e = from[e->v()];
}
s.push(e);
// 从栈中依次取出元素, 获得顺序的从s到w的路径
while( !s.empty() ){
e = s.top();
vec.push_back( *e );
s.pop();
}
}
// 打印出从s点到w点的路径
void showPath(int w){
assert( w >= 0 && w < G.V() );
assert( hasPathTo(w) );
vector<Edge<Weight>> vec;
shortestPath(w, vec);
for( int i = 0 ; i < vec.size() ; i ++ ){
cout<<vec[i].v()<<" -> ";
if( i == vec.size()-1 )
cout<<vec[i].w()<<endl;
}
}
};
main.cpp:
// 测试我们的Dijkstra最短路径算法
int main() {
string filename = "testG1.txt";
int V = 5;
SparseGraph<int> g = SparseGraph<int>(V, true);
// Dijkstra最短路径算法同样适用于有向图
//SparseGraph<int> g = SparseGraph<int>(V, false);
ReadGraph<SparseGraph<int>, int> readGraph(g, filename);
cout<<"Test Dijkstra:"<<endl<<endl;
Dijkstra<SparseGraph<int>, int> dij(g,0);
for( int i = 0 ; i < V ; i ++ ){
if(dij.hasPathTo(i)){
cout<<"Shortest Path to "<<i<<" : "<<dij.shortestPathTo(i)<<endl;
dij.showPath(i);
}
else
cout<<"No Path to "<<i<<endl;
cout<<"----------"<<endl;
}
return 0;
}
运行结果
处理负权边
拥有负权环的不存在最短路径
两边形成负权环
Bellman-Ford 单源最短路径算法
复杂度高
- 如果一个图没有负权环，
- 从一点到另外一点的最短路径，最多经过所有的V个顶线，有V-1条边
- 否则，存在顶点经过了两次，既存在负权环
松弛操作的核心是我们找到了一条边的路径，我们看一下有没有两条边的路径比他权值小。
-
对一个点的一次松弛操作，就是找到经过这个点的另外一条路径，多一条边，权值更小。
-
如果一个图没有负权环，从一点到另外一点的最短路径，最多经过所有的V个顶线，有V-1条边
-
对所有的点进行V-1次松弛操作
-
对所有的点进行V-1次松弛操作，理论上就找到了从源点到其他所有点的最短路径。
-
如果还可以继续松弛，所说原图中有负权环。
// 使用BellmanFord算法求最短路径
template <typename Graph, typename Weight>
class BellmanFord{
private:
Graph &G; // 图的引用
int s; // 起始点
Weight* distTo; // distTo[i]存储从起始点s到i的最短路径长度
vector<Edge<Weight>*> from; // from[i]记录最短路径中, 到达i点的边是哪一条
// 可以用来恢复整个最短路径
bool hasNegativeCycle; // 标记图中是否有负权环
// 判断图中是否有负权环
bool detectNegativeCycle(){
for( int i = 0 ; i < G.V() ; i ++ ){
typename Graph::adjIterator adj(G,i);
for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )
if( from[e->v()] && distTo[e->v()] + e->wt() < distTo[e->w()] )
return true;
}
return false;
}
public:
// 构造函数, 使用BellmanFord算法求最短路径
BellmanFord(Graph &graph, int s):G(graph){
this->s = s;
distTo = new Weight[G.V()];
// 初始化所有的节点s都不可达, 由from数组来表示
for( int i = 0 ; i < G.V() ; i ++ )
from.push_back(NULL);
// 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0
distTo[s] = Weight();
from[s] = new Edge<Weight>(s, s, 0); // 这里我们from[s]的内容是new出来的, 注意要在析构函数里delete掉
// Bellman-Ford的过程
// 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离
for( int pass = 1 ; pass < G.V() ; pass ++ ){
// 每次循环中对所有的边进行一遍松弛操作
// 遍历所有边的方式是先遍历所有的顶点, 然后遍历和所有顶点相邻的所有边
for( int i = 0 ; i < G.V() ; i ++ ){
// 使用我们实现的邻边迭代器遍历和所有顶点相邻的所有边
typename Graph::adjIterator adj(G,i);
for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )
// 对于每一个边首先判断e->v()可达
// 之后看如果e->w()以前没有到达过， 显然我们可以更新distTo[e->w()]
// 或者e->w()以前虽然到达过, 但是通过这个e我们可以获得一个更短的距离, 即可以进行一次松弛操作, 我们也可以更新distTo[e->w()]
if( from[e->v()] && (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]) ){
distTo[e->w()] = distTo[e->v()] + e->wt();
from[e->w()] = e;
}
}
}
hasNegativeCycle = detectNegativeCycle();
}
// 析构函数
~BellmanFord(){
delete[] distTo;
delete from[s];
}
// 返回图中是否有负权环
bool negativeCycle(){
return hasNegativeCycle;
}
// 返回从s点到w点的最短路径长度
Weight shortestPathTo( int w ){
assert( w >= 0 && w < G.V() );
assert( !hasNegativeCycle );
assert( hasPathTo(w) );
return distTo[w];
}
// 判断从s点到w点是否联通
bool hasPathTo( int w ){
assert( w >= 0 && w < G.V() );
return from[w] != NULL;
}
// 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
void shortestPath( int w, vector<Edge<Weight>> &vec ){
assert( w >= 0 && w < G.V() );
assert( !hasNegativeCycle );
assert( hasPathTo(w) );
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
stack<Edge<Weight>*> s;
Edge<Weight> *e = from[w];
while( e->v() != this->s ){
s.push(e);
e = from[e->v()];
}
s.push(e);
// 从栈中依次取出元素, 获得顺序的从s到w的路径
while( !s.empty() ){
e = s.top();
vec.push_back( *e );
s.pop();
}
}
// 打印出从s点到w点的路径
void showPath(int w){
assert( w >= 0 && w < G.V() );
assert( !hasNegativeCycle );
assert( hasPathTo(w) );
vector<Edge<Weight>> vec;
shortestPath(w, vec);
for( int i = 0 ; i < vec.size() ; i ++ ){
cout<<vec[i].v()<<" -> ";
if( i == vec.size()-1 )
cout<<vec[i].w()<<endl;
}
}
};
main.cpp:
// 测试Bellman-Ford算法
int main() {
string filename = "testG2.txt";
//string filename = "testG_negative_circle.txt";
int V = 5;
SparseGraph<int> g = SparseGraph<int>(V, true);
ReadGraph<SparseGraph<int>, int> readGraph(g, filename);
cout<<"Test Bellman-Ford:"<<endl<<endl;
BellmanFord<SparseGraph<int>, int> bellmanFord(g,0);
if( bellmanFord.negativeCycle() )
cout<<"The graph contain negative cycle!"<<endl;
else
for( int i = 1 ; i < V ; i ++ ) {
if (bellmanFord.hasPathTo(i)) {
cout << "Shortest Path to " << i << " : " << bellmanFord.shortestPathTo(i) << endl;
bellmanFord.showPath(i);
}
else
cout << "No Path to " << i << endl;
cout << "----------" << endl;
}
return 0;
}
运行结果：
运行结果
用于有向图，因为无向图中一条负权边就等价于两个方向都有，会形成环。
更多和最短路径相关的问题
单源最短路径算法
具体实现，distTo[i] 初始化为“正无穷”
if( from[e->v()] && (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]) ){
distTo[e->w()] = distTo[e->v()] + e->wt();
from[e->w()] = e;
}
利用队列数据结构
queue-based bellman-ford算法
对比
所有对最短路径算法
Floyed算法，处理无负权环的图
O( V^3 )
最长路径算法
最长路径问题不能有正权环。
无权图的最长路径问题是指数级难度的。
对于有权图，不能使用Dijkstra求最长路径问题。
可以使用 Bellman-Ford算法。（取负操作）
网友评论