В основном он знакомит с проблемой кратчайшего пути и операцией релаксации, идеей алгоритма Дейкстры, ребра с отрицательным весом, алгоритма Беллмана-Форда и т. д.
Задача о кратчайшем пути и операции релаксации
Кратчайший путь от одного узла к другому, задача планирования пути.
- Планирование пути (стоимость, длина)
- планирование рабочих задач
Обход в ширину невзвешенного графа заключается в поиске кратчайшего пути (найденное дерево кратчайших путей)
-
Дерево с кратчайшим путем от начальной точки до других узлов
-
Кратчайший путь невзвешенного графа.
- кратчайший путь
Слабая работа
Операция релаксации означает, что для каждой вершины v∈V устанавливается атрибут d[v], описывающий верхнюю границу веса на кратчайшем пути от исходной точки s до v, которая называется оценкой кратчайшего пути (кратчайшего пути). -путевая оценка).
- Операция релаксации, чтобы найти более короткий путь, операция релаксации является ядром решения кратчайшего пути.
Алгоритм кратчайшего пути из одного источника Дейкстры
ограничение
- Предпосылка: граф не может иметь ребер с отрицательным весом.
- Сложность O( E log(V) ) такая же, как у минимального остовного дерева
Минимальная куча индексов
- Кратчайший путь среди точек, достижимых из исходной точки.
- Граф не может иметь ребер с отрицательным весом
Слабая работа
- После 2 к 1 и после 2 к 3 меньше первоначально записанных значений, поэтому вялое обновление.
- Через 1-4 короче
Код
// 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] );//最小索引堆支持change操作
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;
}
Отрицательные взвешенные ребра и алгоритм Беллмана-Форда
Алгоритм Дейкстры не может обрабатывать отрицательные взвешенные ребра
-
Не существует кратчайшего пути с циклами с отрицательным весом
-
Обе стороны образуют кольцо с отрицательным весом
Алгоритм кратчайшего пути Беллмана-Форда из одного источника
- В графе не может быть отрицательных весовых циклов.
- Беллман-Форд может определить, есть ли в графе отрицательный весовой цикл.
- Кратчайший путь из одной точки в другую, проходящий не более чем через все 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; } -
Используйте структуру данных очереди
-
Алгоритм Беллмана-Форда на основе очереди
Сравнение алгоритмов кратчайшего пути из одного источника
Алгоритм кратчайшего пути для всех пар
- Алгоритм Флойеда, работающий с графами без колец отрицательного веса.
- O( V^3 )
алгоритм наибольшего пути
- Задача о самом длинном пути не может иметь положительных весовых циклов.
- Задача о самом длинном пути для невзвешенных графов экспоненциально сложна.
- Для взвешенных графов Дейкстру нельзя использовать для поиска задачи о самом длинном пути.
- Можно использовать алгоритм Беллмана-Форда. (Отрицательная операция)
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут лайкнуть / подписаться, ваша поддержка - самая большая поддержка для меня.
личный блогСтек томатной технологиииДомашняя страница Наггетс
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт в WeChat: Tomato Technology Stack.