初识最短路
文章目录
最短路算法
Bellman-Ford算法(单源最短路可含负边
原则:不断地用别的点的权值来更新顶点i。
记从起点s出发到顶点i的最短距离是d[i]。
d[i] = min {d[j] + cost (j -> i)|e = (j, i) ∈ E}。重复2nd操作来更新d;经过有限次的操作,结束之后的d就是最短距离。
void dijkstra(int s) {
fill(d, d + V, INF);
fill(used, used + V, false);
d[s] = 0;
for (; ; ) {
int v = -1;
// 从尚未使用过的顶点中选择一个距离最小的顶点
for (int u = 0; u < V; u++) {
if (!used[u] && (v == -1 || d[u] < d[v])) {
v = u;
}
}
if (v == -1) {
used[v] = true;
}
for (int u = 0; u < v; u++) {
d[u] = min(d[u], d[v] + cost[v][u]);
}
}
}
Dijkstra算法(单源最短路不含负边
原则:已标号的点为集合V,未标号的为V的补集;另集合D(P,Q)表示两点之间的最短距离。
源点S上标号为0。(表示
D(S, S) = 0)从S直接相邻(不需要经过第三点即可到达)的所有中挑出最近的点,标上距离,并将这些点放入集合V。
从集合V里的点直接相邻的CuV中挑出距离源点S最近的点标上距离,并将这些点放入集合V。
重复3nd操作,直到V为全集。
int cost[MAX_V][MAX_V]; // cost[u][v]表示边e=(u,v)的权值(不存在这条边时设为INF)
int d[MAX_V]; // 顶点s出发的最短距离
bool used[MAX_V]; // 已经使用过的图
int V; // 顶点数
// 求从起点s出发到各个顶点的最短距离
void dijkstra(int s) {
fill(d, d + V, INF);
fill(used, used + V, false);
d[s] = 0;
for (; ; ) {
int v = -1;
// 从尚未使用过的顶点中选择一个距离最小的顶点
for (int u = 0; u < V; u++) {
if (!used[u] && (v == -1 || d[u] < d[v])) {
v = u;
}
}
if (v == -1) {
used[v] = true;
}
for (int u = 0; u < v; u++) {
d[u] = min(d[u], d[v] + cost[v][u]);
}
}
}
可用“堆”进行优化
// 用堆进行优化
struct edge {
int to, cost;
};
typedef pair<int, int> P;
int V;
vector<edge> G[MAX_V];
int d[MAX_V];
void dijkstra(int s) {
// 通过指定greater<P>参数,堆按照first从小到大的顺序取出值
priority_queue<P, vector<P>, greater<P> > que;
fill(d, d + V, INF);
d[s] = 0;
que.push(P(0,s));
while (!que.empty()) {
P p = que.top();
que.pop();
int v = p.second;
if (d[v] < p.first) {
continue;
}
for (int i = 0; i < G[v].size(); i++) {
edge e = G[v][i];
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
}
Floyd-Warshall算法(任意两点间最短路
原则:贪心(对每一步进行贪心处理)
用n*n的矩阵表示出两点之间的直接距离(从行序号到列序号)。(PS:若两点之间无法直接到达,则用∞/INF来表示)
若要得到出更短的距离,只有在两点之间用第三点来作为中介。
例如,A、B两点之间存在第三点K,若
AK + KB < AB,则用K点更新AB两点之间的距离。重复3nd操作,直到任意两点之间没有第三点可以加入。
void Warshall-Floyd() {
for (int k = 0; k < V; k++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
}
SPFA算法(Shortest Path Faster Algorithm)
适用:可用于存在负权的最短路计算
动态逼近法(逐步找出最短路)
设定一个先进先出的队列(FIFO)。
把队列中第一个的临近点做松弛操作。
若队列中不存在此点,则将此点放入队尾。
删除队首点。
重复2nd~4th操作,直到队列为空。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论