最短路径算法

常见的最短路径算法一般有Floyd，Dijkstra，Johnson，Bellman-Ford算法。按照课本所学的先后顺序，我们先讲Dijkstra。

Dijkstra算法

Dijkstra算法其实是Floyd的优化，成功将$O(n^3)$降到了$O(n^2)$，并且还是采用了动态规划的思想。我们从起点枚举最短路径开始。

比如从A出发，我们会知道首先选择B，其路径为$A\rightarrow B:1$。好的接下来哪个路径最短？首先不能是A到D吧，边权都3了。那应该是2吗？好像是吧。。。

其实不妨这么想，在找到路径之后，都更新路径数组dp[]，这里可以看到，若要A到C，可以选择$A\rightarrow C$，也可以$A\rightarrow B \rightarrow C$，但其实$A\rightarrow C$更短。

所以有了如下的状态转移方程；

$$dp[i] = \min(dp[i], dp[now] + adjmat[now][i])$$

其中$i$是可联通顶点，$now$是刚刚找到的最短路终顶点，$dp[i]$是起点到顶点$i$的最短路径。

暴力解法：

void dijkstra(int s) {
    dis = adjmat[s];
    visit[s] = true;
    for (int i = 1; i < n; i++) {
        int minW = INT_MAXN, now = -1;
        for (int j = 0; j < n; j++) {
            if (!visit[j] && dis[j] <= minW) {
                minW = dis[j];
                now = j;
            }
        }
        if (now == -1) return;
        visit[now] = true;
        for (int j = 0; j < n; j++) {
            if (!visit[j]) dis[j] = min(dis[j], dis[now] + adjmat[now][j]);
        }
    }
    for (auto i: dis) cout << i << ' ';
}

下面是输出路径版本：

void dijkstra(int s) {
    dis = adjmat[s];
    visit[s] = true;
    for(int i = 0; i < n; i++) parent[i] = i;
    for (int i = 1; i < n; i++) {
        int minW = INT_MAXN, now = -1;
        for (int j = 0; j < n; j++) {
            if (!visit[j] && dis[j] <= minW) {
                minW = dis[j];
                now = j;
            }
        }
        if (now == -1) return;
        visit[now] = true;
        for (int j = 0; j < n; j++) {
            if (!visit[j] && dis[now] + adjmat[now][j] < dis[j]) {
                dis[j] = dis[now] + adjmat[now][j];
                parent[j] = now;
            }
        }
    }
    for (auto i: dis) cout << i << ' ';
  	//这里输出路径，思路类似于并查集
    cout << endl;
    for (int i = 1; i < parent.size(); i++) {
        cout << s << "->" << i << " is " << dis[i] << ": 0--";
        int j = i;
        while (j != parent[j]) {
            cout << parent[j] << "--";
            j = parent[j];
        }
        cout << i << endl;
    }
}