最短路

Dijkstra 单源最短路邻接矩阵形式

/* * 单源最短路径，Dijkstra算法，邻接矩阵形式，复杂度为O(n^2) * 求出源beg到所有点的最短路径，传入图的顶点数和邻接矩阵cost[][] * 返回各点的最短路径lowcost[]，路径pre[]，pre[i]记录beg到i路径上的父节点，pre[beg] = -1 * 可更改路径权类型，但是权值必须为非负，下标0~n-1 */
const int MAXN = 1010;
const int INF = 0x3f3f3f3f; // 表示无穷
bool vis[MAXN];
int pre[MAXN];

void Dijkstra(int cost[][MAXN], int lowcost[], int n, int beg)
{
    for (int i = 0; i < n; i++)
    {
        lowcost[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    lowcost[beg] = 0;
    for (int j = 0; j < n; j++)
    {
        int k = -1;
        int min = INF;
        for (int i = 0; i < n; i++)
        {
            if (!vis[i] && lowcost[i] < min)
            {
                min = lowcost[i];
                k = i;
            }
        }
        if (k == -1)
        {
            break;
        }
        vis[k] = true;
        for (int i = 0; i < n; i++)
        {
            if (!vis[i] && lowcost[k] + cost[k][i] < lowcost[i])
            {
                lowcost[i] = lowcost[k] + cost[k][i];
                pre[i] = k;
            }
        }
    }
}

Dijkstra 单源最短路邻接矩阵形式双路径信息

/* * 单源最短路径，dijkstra算法，邻接矩阵形式，复杂度为O(n^2) * 两点间距离存入map[][],两点间花费存入cost[][] * 求出源st到所有点的最短路径及其对应最小花费 * 返回各点的最短路径lowdis[]以及对应的最小花费lowval[] * 可更改路径权类型，但是权值必须为非负，下标1~n */

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;

int n, m;

int lowdis[MAXN];
int lowval[MAXN];
int visit[MAXN];
int map[MAXN][MAXN];
int cost[MAXN][MAXN];

void dijkstra(int st)
{
    int temp = 0;
    for (int i = 1; i <= n; i++)
    {
        lowdis[i] = map[st][i];
        lowval[i] = cost[st][i];
    }
    memset(visit, 0, sizeof(visit));

    visit[st] = 1;
    for (int i = 1; i < n; i++)
    {
        int MIN = INF;
        for (int j = 1; j <= n; j++)
        {
            if (!visit[j] && lowdis[j] < MIN)
            {
                temp = j;
                MIN = lowdis[j];
            }
        }
        visit[temp] = 1;
        for (int j = 1; j <= n; j++)
        {
            if (!visit[j] && map[temp][j] < INF)
            {
                if (lowdis[j] > lowdis[temp] + map[temp][j])
                {
                    lowdis[j] = lowdis[temp] + map[temp][j];
                    lowval[j] = lowval[temp] + cost[temp][j];
                }
                else if (lowdis[j] == lowdis[temp] + map[temp][j])
                {
                    if (lowval[j] > lowval[temp] + cost[temp][j])
                    {
                        lowval[j] = lowval[temp] + cost[temp][j];
                    }
                }
            }
        }
    }

    return ;
}

Dijkstra 起点Start 结点有权值

#define M 505

const int inf = 0x3f3f3f3f;

int num[M];           // 结点权值
int map[M][M];        // 图的临近矩阵
int vis[M];           // 结点是否处理过
int ans[M];           // 最短路径结点权值和
int dis[M];           // 各点最短路径花费
int n, m, Start, End; // n结点数，m边数，Start起点，End终点

void Dij(int v)
{
    ans[v] = num[v];
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; ++i)
    {
        if (map[v][i] < inf)
        {
            ans[i] = ans[v] + num[i];
        }
        dis[i] = map[v][i];
    }
    dis[v] = 0;
    vis[v] = 1;
    for (int i = 1; i < n; ++i)
    {
        int u = 0, min = inf;
        for (int j = 0; j < n; ++j)
        {
            if (!vis[j] && dis[j] < min)
            {
                min = dis[j];
                u = j;
            }
        }
        vis[u] = 1;
        for (int k = 0; k < n; ++k)
        {
            if (!vis[k] && dis[k] > map[u][k] + dis[u])
            {
                dis[k] = map[u][k] + dis[u];
                ans[k] = ans[u] + num[k];
            }
        }
        for (int k = 0; k < n; ++k)
        {
            if (dis[k] == map[u][k] + dis[u])
            {
                ans[k] = max(ans[k], ans[u] + num[k]);
            }
        }
    }
    printf("%d %d\n", dis[End], ans[End]);  // 输出终点最短路径花费、最短路径结点权值和
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &Start, &End);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &num[i]);
    }
    memset(vis, 0, sizeof(vis));
    memset(map, 0x3f, sizeof(map));
    for (int i = 0; i < m; ++i)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if (map[x][y] > z)
        {
            map[x][y] = z;
            map[y][x] = z;
        }
    }
    Dij(Start);

    return 0;
}

Dijkstar 堆优化

/* * 使用优先队列优化Dijkstra算法 * 复杂度O(ElongE) * 注意对vector<Edge> E[MAXN]进行初始化后加边 */

const int INF = 0x3f3f3f3f;
const int MAXN = 1000010;

struct qNode
{
    int v;
    int c;
    qNode(int _v = 0, int _c = 0) : v(_v), c(_c) {}
    bool operator < (const qNode &r) const
    {
        return c > r.c;
    }
};

struct Edge
{
    int v;
    int cost;
    Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};

vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];     // 最短路距离

void Dijkstra(int n, int start)     // 点的编号从1开始
{
    memset(vis, false, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<qNode> que;

    while (!que.empty())
    {
        que.pop();
    }
    dist[start] = 0;
    que.push(qNode(start, 0));
    qNode tmp;

    while (!que.empty())
    {
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if (vis[u])
        {
            continue;
        }
        vis[u] = true;
        for (int i = 0; i < E[u].size(); i++)
        {
            int v = E[u][i].v;
            int cost = E[u][i].cost;
            if (!vis[v] && dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                que.push(qNode(v, dist[v]));
            }
        }
    }
}

void addEdge(int u, int v, int w)
{
    E[u].push_back(Edge(v, w));
}

单源最短路 BellmanFord算法

/* * 单源最短路BellmanFord算法，复杂度O(VE) * 可以处理负边权图 * 可以判断是否存在负环回路，返回true，当且仅当图中不包含从源点可达的负权回路 * vector<Edge> E;先E.clear()初始化，然后加入所有边 */

const int INF = 0x3f3f3f3f;
const int MAXN = 550;
int dist[MAXN];
struct Edge
{
    int u;
    int v;
    int cost;
    Edge(int _u = 0, int _v = 0, int _cost = 0) : u(_u), v(_v), cost(_cost){}
};

vector<Edge> E;

bool BellmanFord(int start, int n)  // 编号从1开始
{
    memset(dist, 0x3f, sizeof(dist));
    dist[start] = 0;
    for (int i = 1; i < n; i++)     // 最多做n - 1次
    {
        bool flag = false;
        for (int j = 0; j < E.size(); j++)
        {
            int u = E[j].u;
            int v = E[j].v;
            int cost = E[j].cost;
            if (dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                flag = true;
            }
        }
        if (!flag)                  // 无负环回路
        {
            return true;
        }
    }
    for (int j = 0; j < E.size(); j++)
    {
        if (dist[E[j].v] > dist[E[j].u] + E[j].cost)
        {
            return false;           // 有负环回路
        }
    }

    return true;                    // 无负环回路
}

单源最短路 SPFA

/* * 时间复杂度O(kE) * 队列实现，有时候改成栈实现会更快，较容易修改 */

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;

struct Edge
{
    int v;
    int cost;
    Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};

vector<Edge> E[MAXN];

void addEdge(int u, int v, int w)
{
    E[u].push_back(Edge(v, w));
}

bool vis[MAXN];     // 在队列标志
int cnt[MAXN];      // 每个点的入列队次数
int dist[MAXN];

bool SPFA(int start, int n)
{
    memset(vis, false, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));

    vis[start] = true;
    dist[start] = 0;
    queue<int> que;

    while (!que.empty())
    {
        que.pop();
    }
    que.push(start);
    memset(cnt, 0, sizeof(cnt));
    cnt[start] = 1;

    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        vis[u] = false;

        for (int i = 0; i < E[u].size(); i++)
        {
            int v = E[u][i].v;
            if (dist[v] > dist[u] + E[u][i].cost)
            {
                dist[v] = dist[u] + E[u][i].cost;
                if (!vis[v])
                {
                    vis[v] = true;
                    que.push(v);
                    if (++cnt[v] > n)
                    {
                        return false;   // cnt[i]为入队列次数，用来判定是否存在负环回路
                    }
                }
            }
        }
    }

    return true;
}

Floyd算法邻接矩阵形式

/*
 *  Floyd算法，求从任意节点i到任意节点j的最短路径
 *  cost[][]:初始化为INF（cost[i][i]：初始化为0）
 *  lowcost[][]:最短路径，path[][]:最短路径（无限制）
 */
const int MAXN = 100;

int cost[MAXN][MAXN];
int lowcost[MAXN][MAXN];
int path[MAXN][MAXN];

void Floyd(int n)
{
 memcpy(lowcost, cost, sizeof(cost));
 memset(path, -1, sizeof(path));

 for (int k = 0; k < n; k++)
 {
   
 for (int i = 0; i < n; i++)
 {
   
 for (int j = 0; j < n; j++)
 {
   
 if (lowcost[i][j] > (lowcost[i][k] + lowcost[k][j]))
 {
   
 lowcost[i][j] = lowcost[i][k] + lowcost[k][j];
 path[i][j] = k;
 }
 }
 }
 }
 return ;
}

Floyd算法点权 + 路径限制

/*
 *  Floyd算法，求从任意节点i到任意节点j的最短路径
 *  cost[][]:初始化为INF（cost[i][i]：初始化为0）
 *  val[]:点权，lowcost[][]:除起点、终点外的点权之和+最短路径
 *  path[][]:路径限制，要求字典序最小的路径，下标1~N
 */
const int MAXN = 110;
const int INF = 0x1f1f1f1f;

int val[MAXN];          //  点权
int cost[MAXN][MAXN];
int lowcost[MAXN][MAXN];
int path[MAXN][MAXN];   //  i~j路径中的第一个结点

void Floyd(int n)
{
 memcpy(lowcost, cost, sizeof(cost));
 for (int i = 0; i <= n; i++)
 {
   
 for (int j = 0; j <= n; j++)
 {
   
 path[i][j] = j;
 }
 }

 for (int k = 1; k <= n; k++)
 {
   
 for (int i = 1; i <= n; i++)
 {
   
 for (int j = 1; j <= n; j++)
 {
   
 int temp = lowcost[i][k] + lowcost[k][j] + val[k];
 if (lowcost[i][j] > temp)
 {
   
 lowcost[i][j] = temp;
 path[i][j] = path[i][k];
 }
 else if (lowcost[i][j] == temp && path[i][j] > path[i][k])
 {
   
 path[i][j] = path[i][k];
 }
 }
 }
 }
 return ;
}