寻找最短路径 – 图表示与经典算法

最短路径

链式前向星

图的链式前向星表示法是邻接表的改进，仅将邻接表的边链接改为数组实现， 存储空间更小。vertex数组索引作为图节点编号，edge数组存边，索引作为每条边的地址，实现如下

int cnt;
int vertex[V];
 
struct Edge {
    int next;
    int to;
    double weight;
} edge[E];
 
void addEdge(int s, int to, double weight) {
    edge[cnt].to = to;
    edge[cnt].weight = weight;
    edge[cnt].next = vertex[s];
    vertex[s] = cnt++;
}

BFS

int visited[V];

void BFS(int s) {
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(edge e: v.edges())
            if(!visited[e.to])
                q.push(e.to);
    }
}

队列优化的Bellman-Ford

概述

经典的Bellman-Ford算法以BFS方式扩散至图中每一个节点和每一条边，每轮访问所有边，更新所有可以计算出更短路径的节点。

细节

每轮更新 至少有一个节点更新成为到达某点的最短路径的子路径 ，更新顶点数量轮可保证获得全局最短路径。

负环是指环路边权值和为负数。现在说明 图中无源点可达的负环时，即使不进行BFS中的访问节点标记也不会陷入无限循环：算法每次寻到节点的更优值都会将节点重新进入队列扩散更新周边节点路径长度，节点达最优之后所有对节点的重复访问都是更长路径被更新条件剪枝，当且仅当所有节点达到最优值时算法停止。例设有向边\scriptsize u\xrightarrow{len=3}v，\scriptsize v\xrightarrow{len=-1}u。从u开始扩散到v，再由v扩散回到u时一定是u→u的更长路径被更新条件剪枝。

以下说明源点可达的负环检测。由于负环可一直使环路权值和继续递减，因此会逐步占据优势成为最短路径，并继续递减 陷入无限循环。不存在负环的经典算法中，顶点数轮是可以保证算法结束的，由此只要运行轮数大于总顶点数轮则一定存在负环。队列优化的Bellman-Ford轮数无法显式控制，以某顶点重复访问次数大于总顶点数来判断。

源点不可达的负环检测可构造一个虚拟节点v来使源点s和图中所有其他节点u均联通 \scriptsize s \rightarrow v \rightarrow u_i，成为源点可达的负环检测问题。

优化实现

以下算法使用队列对Bellman-Ford的节点扩散做出优化，每轮中 仅扩散获得累积路径更短的节点，避免了不必要的扩散计算。该算法又称为SPFA。

const double INF = DBL_MAX;
const int E = 100;
const int V = 100;
double dis[V];
int vertex[V];
int path[V];
int inq[V];
int num[V];

void init() {
    cnt = 0;
    memset(vertex, -1, sizeof(vertex));
    memset(path, -1, sizeof(path));
    memset(inq, 0, sizeof(inq));
    memset(num, 0, sizeof(num));
    fill(dis, dis + V, INF);
    for (int i = 0; i < E; i++)
        edge[i].next = -1;
}

bool spfa(int s) {
    init();
    queue<int> q;
    q.push(s);
    dis[s] = 0.0;

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = 0;
        Edge e;

        for (int i = vertex[v]; ~i; i = edge[i].next) {
            e = edge[i];
            if (dis[v] + e.weight < dis[e.to]) {
                dis[e.to] = dis[v] + e.weight;
                path[e.to] = v;
                if (!inq[e.to]) {
                    if(num[e.to]++ > V) return true;
                    q.push(e.to);
                    inq[e.to] = 1;
                }
            }
        }
    }

    return false;
}

优先队列优化的Dijkstra

概述

Dijkstra算法从源节点以BFS方式扩散至图中每一个节点和每一条边，每次均选择距离源点最近的节点扩散，通过最优子结构推广到全局最优。

细节

从运行过程上来理解：仅考虑源到目标节点的多条路径，每条路径均会扩散至目标节点。若最短路径优于已探索的非最优路径的子路径，由于算法 总选择最短路径向外扩散，最短路径一定优先到达目标节点，且仍是当前所有已探索路径中的最短路径。若非最优路径的子路径优于最短路径，算法会选择非最优路径扩散先到达目标节点，而此时的总路径一定长于最短路径的子路径p，算法会选择p扩散至目标节点，仍是所有已探索路径中的最短路径。

关于扩散过程中不标记已访问节点不会导致无限循环问题，理由同Bellman-Ford。

Dijkstra算法在图中有负权边时可能会导致算法出错无法继续进行。

目标节点可达性问题，即算法结束后判断 \scriptsize s \xrightarrow{len=\infty?} u 问题

优化实现

节点从第一次访问时进入队列，之后访问到该节点时 要么达到最优已出队列 ，已进行了最优值的扩散更新，无需再进行更新条件判断，要么还 未达到最优在队列中 未开始扩散，仅更新节点值，待后续达到最优出队时扩散更新周边节点即可。以下算法做出两处优化，每个节点仅进入队列一次，避免重复扩散和计算

const double INF = __DBL_MAX__;
const int V = 15;
const int E = 15;
double dist[V];
int path[V];
int done[V];
int inq[V];

struct Cmp {
    bool operator()(int u, int v) {
        return dist[u] > dist[v];
    }
};

void init() {
    cnt = 0;
    memset(path, -1, sizeof(path));
    memset(vertex, -1, sizeof(vertex));
    memset(inq, 0, sizeof(inq));
    memset(done, 0, sizeof(done));
    fill(dist, dist + V, INF);
    for (int i = 0; i < E; i++)
        edge[i].next = -1;
}

void dijkstra(int s) {
    priority_queue<int, vector<int>, Cmp> q;
    q.push(s);
    dist[s] = 0.0;

    while (!q.empty()) {
        int v = q.top();
        done[v] = 1;
        inq[v] = 0;
        q.pop();
        for (int i = vertex[v]; ~i; i = edge[i].next) {
            Edge e = edge[i];
            double w = e.weight;
            int t = e.to;
            if (done[t]) continue;
            if (dist[v] + w < dist[t]) {
                dist[t] = dist[v] + w;
                path[t] = v;
                if(!inq[t]) { q.push(t); inq[t] = 1;}
            }
        }
    }
}

bool hasPathTo(int v) {
    return dist[v] < INF;
}

void printPath(int v) {
    int t = path[v];
    if (~t) printPath(t);
    printf("%d ->", v);
}

void printPathTo(int v) {
    if (hasPathTo(v)) printPath(v);
    else printf("No Path to %d", v);
}

int main() {
    init();
    int v, e;
    while (~scanf("%d%d", &v, &e)) {
        while (e--) {
            int s, t;
            double w;
            scanf("%d%d%lf", &s, &t, &w);
            addEdge(s, t, w);
        }
    }

    int s, t;
    dijkstra(s);
    printPathTo(t);
    return 0;
}

Floyd-Warshall

概述

枚举所有i到j的路径i->k->j，取枚举最优值更新

细节

若i->j的路径可表示为d[i][j]，则最短路径的更新条件可表示为\scriptsize d[i][k] + d[k][j] \lt d[i][j] 动态规划转移方程为 \scriptsize dp[i][j] = min(dp[i][j], dp[i][k] + d[k][j])

将 k置于最外层 保证k始终小于等于i,j，否则置于i,j内部优先枚举k时，子问题dp[i][k]与dp[k][j]还未计算最优，破坏了最优子结构性质，状态转移会出错。举个例子，若k置于最内层，则k会先大于i和j，如 \scriptsize i=2,j=4,k=6 时，\scriptsize dp[2][4]=dp[2][6]+dp[6][2]，此时最优结果dp[i][j]还未枚举计算 \scriptsize dp[2][6]、dp[6][2] 最优值因而导致计算结果错误。

当图中存在负环时，绕一圈后回来路径最短，dp[i][i]一定是负值

优化实现

无dp[i][k]边时，可减少一轮枚举

const double INF = DBL_MAX;
const int V = 100;
double dp[V][V];

void init() {
    fill(dp, dp + V * V, INF);
    int s, t;
    double w;
    while(~scanf("%d%d%lf", &u, &v, &w))
        dp[u][v] = dp[v][u] = w;
}

bool hasNegativeCircle() {
    for(int i = 0; i < V; i++)
        if(dp[i][i] < 0)
            return true;
    return false;
}

void floyd() {
    init();
    for(k = 0; k < V; k++)
        for(int i = 0; i < V; i++)
            if(dp[i][k] != INF)
            for(int j = 0; j < V; j++)
                if(dp[i][k] + dp[k][j] < dp[i][j])
                    dp[i][j] = dp[i][k] + dp[k][j];
    hasNegativeCircle();
}

搜索方法

详见搜索进阶中 A* 方法及其变种