初识最短路

最短路算法

Bellman-Ford算法(单源最短路可含负边

原则:不断地用别的点的权值来更新顶点i。

  1. 记从起点s出发到顶点i的最短距离是d[i]。

  2. d[i] = min {d[j] + cost (j -> i)|e = (j, i) ∈ E}。

  3. 重复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)表示两点之间的最短距离。

  1. 源点S上标号为0。(表示D(S, S) = 0)

  2. 从S直接相邻(不需要经过第三点即可到达)的所有中挑出最近的点,标上距离,并将这些点放入集合V。

  3. 从集合V里的点直接相邻的CuV中挑出距离源点S最近的点标上距离,并将这些点放入集合V。

  4. 重复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算法(任意两点间最短路

原则:贪心(对每一步进行贪心处理)

  1. 用n*n的矩阵表示出两点之间的直接距离(从行序号到列序号)。(PS:若两点之间无法直接到达,则用∞/INF来表示)

  2. 若要得到出更短的距离,只有在两点之间用第三点来作为中介。

  3. 例如,A、B两点之间存在第三点K,若AK + KB < AB,则用K点更新AB两点之间的距离。

  4. 重复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)

适用:可用于存在负权的最短路计算

动态逼近法(逐步找出最短路)
  1. 设定一个先进先出的队列(FIFO)。

  2. 把队列中第一个的临近点做松弛操作。

  3. 若队列中不存在此点,则将此点放入队尾。

  4. 删除队首点。

  5. 重复2nd~4th操作,直到队列为空。

评论

暂无评论