最短路径

Dijkstra算法：

邻接矩阵：

#include <algorithm>

using namespace std;
const int maxn = 1010;
const int INF = 1 << 30;

int G[maxn][maxn];
int d[maxn];//起点到达各顶点的最短路径长度
int pre[maxn];//pre[v]表示从起点到顶点v的最短路径上v的前一个顶点
bool isVisit[maxn];
int n;

void dijkstra(int st) {
    fill(d, d + maxn, INF);
    d[st] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, min = INF;
        for (int j = 0; j < n; j++) {
            if (isVisit[j] == false && d[j] < min) {
                u = j;
                min = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        isVisit[u] = true;
        for (int j = 0; j < n; j++) {
            if (isVisit[j] == false && G[u][j] != INF && d[u] + G[u][j] < d[j]) {
                d[j] = d[u] + G[u][j];
                pre[j] = u;
            }
        }
    }
}

//起点s到顶点v的最短路径
void dfs(int s, int v) {
    if (v == s) {
        printf("%d\n", s);
        return;
    }
    dfs(s, pre[v]);
    printf("%d\n", v);
}

邻接表：

#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 1010;
const int INF = 1 << 30;
struct Node {
    int v, dis;
};

vector<Node> G[maxn];
int n;
int d[maxn];
int pre[maxn];//pre[v]表示从起点到顶点v的最短路径上v的前一个顶点
bool isVisit[maxn];

void dijkstra(int st) {
    fill(d, d + maxn, INF);
    d[st] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, min = INF;
        for (int j = 0; j < n; j++) {
            if (isVisit[j] == false && d[j] < min) {
                u = j;
                min = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        isVisit[u] = true;
        for (int j = 0; j < G[u].size(); j++) {
            int v = G[u][j].v;
            if (isVisit[v] == false && d[u] + G[u][j].dis < d[v]) {
                d[v] = d[u] + G[u][j].dis;
                pre[v] = u;
            }
        }
    }
}

void dfs(int s, int v) {
    if (v == s) {
        printf("%d\n", s);
        return;
    }
    dfs(s, pre[v]);
    printf("%d\n", v);
}

dijkstra+DFS解决单源点最短路径通用方案：

1.先用万能模板记录所有最短路径（无需修改任何代码）。

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXV = 510;//最大顶点数
const int INF = 1000000000;//无穷大
//n为顶点数，m为边数，start为起点，end为终点，G为邻接矩阵
int n, m, start, end, G[MAXV][MAXV];
//d记录到起点的最短距离
int d[MAXV];
bool isVisit[MAXV] = {false};//true表示顶点i已访问

vector<int> pre[MAXV];//存放结点v的所有能产生最短路径的前驱结点

void dijkstra(int s) {//s为起点
    fill(d, d + MAXV, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (isVisit[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        isVisit[u] = true;
        for (int j = 0; j < n; j++) {
            if (isVisit[j] == false && d[u] + G[u][j] < d[j]) {
                d[j] = d[u] + G[u][j];
                pre[j].clear();
                pre[j].push_back(u);
            } else if (isVisit[j] == false && d[u] + G[u][j] == d[j]) {
                pre[j].push_back(u);
            }
        }
    }
}

2.遍历所有最短路径，找出一条使第二标尺最优的路径。

void dfs(int v) {//v为当前结点
    tempPath.push_back(v);//将当前结点加入临时路径最后面
    if (v == st) {
        num++;
        int value = 0;//存放临时路径tempPath上第二标尺的值
        计算路径tempPath上的value值;
        if (value优于optValue) {
            optValue = value;
            path = tempPath;
        }
        tempPath.pop_back();
        return;
    }
    //递归式
    for (int i = 0; i < pre[v].size(); i++) {
        dfs(pre[v][i]);//结点v的前驱结点pre[v][i]，递归
    }
    tempPath.pop_back();//遍历完所有前驱结点，将当前结点v删除
}

1003 Emergency

1018 Public Bike Management

1030 Travel Plan

1072 Gas Station

1087 All Roads Lead to Rome

Floyd算法：

const int maxn = 210;
const int INF = 1 << 30;
int n, m;//顶点数，边数
int dis[maxn][maxn];//dis[i][j]表示i和j的最短距离

void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dis[i][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}