最短路径算法
无权图的最短路径
带权图的最短路径
Dijkstra单源最短路径算法
前提：图中不能有负权边
图1
testG1.txt
5 8
0 1 5
0 2 2
0 3 6
1 4 1
2 1 1
2 4 5
2 3 3
3 4 2
读图的类
//
// Created by mozhenhai on 2021/8/4.
//
#ifndef SHORTESTPATH_READGRAPH_H
#define SHORTESTPATH_READGRAPH_H
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <cassert>
using namespace std;
template<typename Graph, typename Weight>
// 读取图算法
class ReadGraph {
public:
// 从文件filename中读取图的信息, 存储进图graph中
ReadGraph(Graph &graph, const string &filename) {
ifstream file(filename);
string line;
int V, E;
assert(file.is_open());
// 第一行读取图中的节点个数和边的个数
assert(getline(file, line));
stringstream ss(line);
ss >> V >> E;
// 读取每一条边的信息
for (int i = 0; i < E; i++) {
assert(getline(file, line));
stringstream ss(line);
int a, b;
Weight w;
ss >> a >> b >> w;
assert(a >= 0 && a < V);
assert(b >= 0 && b < V);
graph.addEdge(a, b, w);
}
}
};
#endif //SHORTESTPATH_READGRAPH_H
边类
//
// Created by mozhenhai on 2021/8/4.
//
#ifndef SHORTESTPATH_EDGE_H
#define SHORTESTPATH_EDGE_H
#include <iostream>
#include <cassert>
using namespace std;
template<typename Weight>
class Edge {
private:
int a, b; //边的两个端点
Weight weight;//边的权值
public:
Edge(int a, int b, Weight weight) {
this->a = a;
this->b = b;
this->weight = weight;
}
Edge() {}
~Edge() {}
int v() {
return a;
}
int w() {
return b;
}
Weight wt() {
return weight;
}
int other(int x) {
assert(x == a || x == b);
return x == a ? b : a;
}
//重载
friend ostream &operator<<(ostream &os, const Edge &e) {
os << e.a << "-" << e.b << ": " << e.weight;
return os;
}
//比较运算符重载
bool operator<(Edge<Weight> &e) {
return weight < e.wt();
}
bool operator<=(Edge<Weight> &e) {
return weight <= e.wt();
}
bool operator>(Edge<Weight> &e) {
return weight > e.wt();
}
bool operator>=(Edge<Weight> &e) {
return weight >= e.wt();
}
bool operator==(Edge<Weight> &e) {
return weight == e.wt();
}
};
#endif //SHORTESTPATH_EDGE_H
稀疏图类
//
// Created by mozhenhai on 2021/8/4.
//
#ifndef SHORTESTPATH_SPARSEGRAPH_H
#define SHORTESTPATH_SPARSEGRAPH_H
#include <iostream>
#include <vector>
#include <cassert>
#include "Edge.h"
// 稀疏图 - 邻接表
template<typename Weight>
class SparseGraph {
private:
int n;//点的个数
int m;//边的个数
bool directed; //是否为有向图
vector<vector<Edge<Weight> *>> g; // 图的具体数据
public:
//构造函数
SparseGraph(int n, bool directed) {
assert(n >= 0);
this->n = n;
this->m = 0;
this->directed = directed;// 初始化没有任何边
// g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
g = vector<vector<Edge<Weight> *>>(n, vector<Edge<Weight> *>());
}
//析构函数
~SparseGraph() {
for (int i = 0; i < n; i++)
for (int j = 0; j < g[i].size(); j++)
double g[i][j];
}
int V() {
return n;//返回点的个数
}
int E() {
return m;//返回边的个数
}
//向图中添加一个边
void addEdge(int v, int w, Weight weight) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
//
// if(hasEdge(v,w))
// return;
g[v].push_back(new Edge<Weight>(v, w, weight));
if (v != w && !directed)
g[w].push_back(new Edge<Weight>(w, v, weight));
m++;
}
//验证图中是否有从v到w的边
bool hasEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
for (int i = 0; i < g[v].size(); i++) {
if (g[v][i]->other(v) == w)
return true;
}
return false;
}
void show() {
for (int i = 0; i < n; i++) {
cout << "vertex " << i << ":\t";
for (int j = 0; j < g[i].size(); j++) {
cout << "(to:" << g[i][j]->w() << ",wt:" << g[i][j]->wt() << ")\t";
}
cout << endl;
}
}
// 邻边迭代器, 传入一个图和一个顶点,
// 迭代在这个图中和这个顶点向连的所有顶点
class adjIterator {
private:
SparseGraph &G; // 图G的引用
int v;
int index;
public:
//构造函数
adjIterator(SparseGraph &graph, int v) : G(graph) {
this->v = v;
this->index = 0;
}
//析构函数
~adjIterator() {}
// 返回图G中与顶点v相连接的第一个顶点
// 若没有顶点和v相连接, 则返回-1
Edge<Weight> *begin() {
index = 0;
if (G.g[v].size())
return G.g[v][index];
return NULL;
}
// 返回图G中与顶点v相连接的下一个顶点
Edge<Weight> *next() {
index++;
if (index < G.g[v].size())
return G.g[v][index];
// 若没有顶点和v相连接, 则返回-1
return NULL;
}
// 查看是否已经迭代完了图G中与顶点v相连接的所有顶点
bool end() {
return index >= G.g[v].size();
}
};
};
#endif //SHORTESTPATH_SPARSEGRAPH_H
稠密图类
//
// Created by mozhenhai on 2021/8/4.
//
#ifndef SHORTESTPATH_DENSEGRAPH_H
#define SHORTESTPATH_DENSEGRAPH_H
#include <iostream>
#include <vector>
#include <cassert>
#include "Edge.h"
using namespace std;
// 稠密图 - 邻接矩阵
template<typename Weight>
class DenseGraph {
private:
int n, m;//n顶点 m 边
bool directed;// 是否为有向图
vector<vector<Edge<Weight> *>> g;// 图的具体数据 为什么存指针，为了方便表达空这个概念
public:
//构造函数
DenseGraph(int n, bool directed) {
assert(n >= 0);
this->n = n;
this->m = 0;// 初始化没有任何边
this->directed = directed;
// g初始化为n*n的矩阵, 每一个g[i][j]指向一个边的信息, 初始化为NULL
g = vector<vector<Edge<Weight> *>>(n, vector<Edge<Weight> *>(n, NULL));
}
//析构函数
~DenseGraph() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (g[i][j] != NULL)
delete g[i][j];
}
int V() {
return n;//返回节点个数
}
int E() {
return m;//返回边的个数
}
//向图中添加一个边
void addEdge(int v, int w, Weight weight) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
//覆盖 如果从v到w已经有边, 删除这条边
if (hasEdge(v, w)) {
delete g[v][w];
if (!directed)
delete g[w][v];
m--;
}
g[v][w] = new Edge<Weight>(v, w, weight);
if (!directed)
g[w][v] = new Edge<Weight>(w, v, weight);
m++;
}
//验证图中是否有从v到w的边
bool hasEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
return g[v][w] != NULL;
}
void show() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
if (g[i][j])
cout << g[i][j]->wt() << "\t";
else
cout << "NULL\t";
cout << endl;
}
}
// 邻边迭代器, 传入一个图和一个顶点,
// 迭代在这个图中和这个顶点向连的所有顶点
class adjIterator {
private:
DenseGraph &G; // 图G的引用
int v;
int index;
public:
// 构造函数
adjIterator(DenseGraph &graph, int v) : G(graph) {
assert(v >= 0 && v < G.n);
this->v = v;
this->index = -1; // 索引从-1开始, 因为每次遍历都需要调用一次next()
}
~adjIterator() {}
// 返回图G中与顶点v相连接的第一个顶点
Edge<Weight> *begin() {
// 索引从-1开始, 因为每次遍历都需要调用一次next()
index = -1;
return next();
}
// 返回图G中与顶点v相连接的下一个顶点
Edge<Weight> *next() {
// 从当前index开始向后搜索, 直到找到一个g[v][index]为true
for (index += 1; index < G.V(); index++)
if (G.g[v][index])
return index;
// 若没有顶点和v相连接, 则返回-1
return NULL;
}
// 查看是否已经迭代完了图G中与顶点v相连接的所有顶点
bool end() {
return index >= G.V();
}
};
};
#endif //SHORTESTPATH_DENSEGRAPH_H
最小索引堆
//
// Created by mozhenhai on 2021/8/4.
//
#ifndef SHORTESTPATH_INDEXMINHEAP_H
#define SHORTESTPATH_INDEXMINHEAP_H
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
template<typename Item>
// 最小索引堆
class IndexMinHeap {
private:
Item *data; // 最小索引堆中的数据
int *indexes; // 最小索引堆中的索引, indexes[x] = i 表示索引i在x的位置
int *reverse; // 最小索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置
int count;
int capacity;
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
void shiftUp(int k) {
while (k > 1 && data[indexes[k / 2]] > data[indexes[k]]) {
swap(indexes[k / 2], indexes[k]);
reverse[indexes[k / 2]] = k / 2;
reverse[indexes[k]] = k;
k = k / 2;
}
}
void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;
if (j + 1 <= count && data[indexes[j]] > data[indexes[j + 1]]) j++;
if (data[indexes[k]] <= data[indexes[j]]) break;
swap(indexes[k], indexes[j]);
reverse[indexes[k]] = k;
reverse[indexes[j]] = j;
k = j;
}
}
public:
// 构造函数, 构造一个空的索引堆, 可容纳capacity个元素
IndexMinHeap(int capacity) {
data = new Item[capacity + 1];
indexes = new int[capacity + 1];
reverse = new int[capacity + 1];
for (int i = 0; i <= capacity; i++)
reverse[i] = 0;
count = 0;
this->capacity = capacity;
}
~IndexMinHeap() {
delete[] data;
delete[] indexes;
delete[] reverse;
}
// 返回索引堆中的元素个数
int size() {
return count;
}
// 返回一个布尔值, 表示索引堆中是否为空
bool isEmpty() {
return count == 0;
}
// 向最小索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
// 传入的i对用户而言,是从0索引的
void insert(int index, Item item) {
assert(count + 1 <= capacity);
assert(index + 1 >= 1 && index + 1 <= capacity);
index += 1;
data[index] = item;
indexes[count + 1] = index;
reverse[index] = count + 1;
count++;
shiftUp(count);
}
// 从最小索引堆中取出堆顶元素, 即索引堆中所存储的最小数据
Item extractMin() {
assert(count > 0);
Item ret = data[indexes[1]];
swap(indexes[1], indexes[count]);
reverse[indexes[count]] = 0;
reverse[indexes[1]] = 1;
count--;
shiftDown(1);
return ret;
}
// 从最小索引堆中取出堆顶元素的索引
int extractMinIndex() {
assert(count > 0);
int ret = indexes[1] - 1;
swap(indexes[1], indexes[count]);
reverse[indexes[count]] = 0;
reverse[indexes[1]] = 1;
count--;
shiftDown(1);
return ret;
}
// 获取最小索引堆中的堆顶元素
Item getMin() {
assert(count > 0);
return data[indexes[1]];
}
// 获取最小索引堆中的堆顶元素的索引
int getMinIndex() {
assert(count > 0);
return indexes[1] - 1;
}
// 看索引i所在的位置是否存在元素
bool contain(int index) {
return reverse[index + 1] != 0;
}
// 获取最小索引堆中索引为i的元素
Item getItem(int index) {
assert(contain(index));
return data[index + 1];
}
// 将最小索引堆中索引为i的元素修改为newItem
void change(int index, Item newItem) {
assert(contain(index));
index += 1;
data[index] = newItem;
shiftUp(reverse[index]);
shiftDown(reverse[index]);
}
};
#endif //SHORTESTPATH_INDEXMINHEAP_HDIJKSTRA算法实现
//
// Created by mozhenhai on 2021/8/4.
//
#ifndef SHORTESTPATH_DIJKSTRA_H
#define SHORTESTPATH_DIJKSTRA_H
#include <iostream>
#include <vector>
#include <stack>
#include <cassert>
#include "Edge.h"
#include "IndexMinHeap.h"
using namespace std;
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());
//Dijkstra
// 对于其实点s进行初始化
distTo[s] = Weight();
from[s] = new Edge<Weight>(s, s, Weight());
marked[s] = true;
ipq.insert(s, distTo[s]);
while (!ipq.isEmpty()) {
// distTo[v]就是s到v的最短距离
int v = ipq.extractMinIndex();
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;
}
// 返回从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;
}
}
};
#endif //SHORTESTPATH_DIJKSTRA_H
测试
//
// Created by mozhenhai on 2021/8/4.
//
#ifndef SHORTESTPATH_TEST_H
#define SHORTESTPATH_TEST_H
#include "DenseGraph.h"
#include "SparseGraph.h"
#include "ReadGraph.h"
#include "Dijkstra.h"
#include "BellmanFord.h"
// 测试我们的Dijkstra最短路径算法
void testDijkstra() {
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 = 1; 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;
}
}
#endif //SHORTESTPATH_TEST_H
主函数
#include <iostream>
#include "test.h"
int main() {
std::cout << "Hello, World!" << std::endl;
testDijkstra();
return 0;
}
Test Dijkstra:
Shortest Path to 1 : 3
0 -> 2 -> 1
----------
Shortest Path to 2 : 2
0 -> 2
----------
Shortest Path to 3 : 5
0 -> 2 -> 3
----------
Shortest Path to 4 : 4
0 -> 2 -> 1 -> 4
----------
Process finished with exit code 0