【图论】最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 10000
int head[MAX]; //代表一个结点，也是子结点链的起点
int edge[MAX]; //储存边的值
int son[MAX]; //子结点链
int ver[MAX]; //代表有向边
int dist[MAX]; //最短路
bool tag[MAX]; //标记结点
int tot = 0; // 边的数量
using namespace std;
void Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist)); //初始化dist
    memset(tag, 0, sizeof(tag)); //初始化tag
    dist[1] = 0; //设置起点
    //计算除终点以外的结点出发的子结点的最短路
    for(int i = 1; i < N; i++)
    {
        int crd = 0; //父结点下标
        //遍历N个结点，找到dist最小的结点
        for(int j = 1; j <= N; j++)
        {
            if(!tag[j] && (crd == 0 || dist[crd] > dist[j]))
            {
                crd = j;
            }
        }
        tag[crd] = true; //标记已经走过的点
        //遍历此结点的子结点
        for(int j = head[crd]; j; j = son[j])
        {
            int ne = ver[j];
            dist[ne] = min(dist[ne], dist[crd] + edge[j]); //更新子结点的dist
        }
    }
    return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#define MAX 10000
int head[MAX]; //代表一个结点，也是子结点链的起点
int edge[MAX]; //储存边的值
int son[MAX]; //子结点链
int ver[MAX]; //代表有向边
int dist[MAX]; //最短路
bool tag[MAX]; //标记结点
int tot = 0; // 边的数量
using namespace std;
//pair的第一维是dist的相反数（把大根堆转换成小根堆）
//pair的第二维是结点下标
priority_queue<pair<int int>> q; //用二叉堆存结点
void Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist)); //初始化dist
    memset(tag, 0, sizeof(tag)); //初始化tag
    dist[1] = 0; //设置起点
    q.push(make_pair(0, 1)); //把起点加入二叉堆
    //一直计算直到队列为空
    while(q.size())
    {
        int crd = q.top().second; //父结点下标
        q.pop(); //移出二叉堆
        if(tag[crd]) continue; //确保此结点没有被扩展过
        tag[crd] = true; //标记已经走过的点
        //遍历此结点的子结点
        for(int j = head[crd]; j; j = son[j])
        {
            if(dist[crd] + edge[j] < dist[ne])
            {
                 dist[ne] = dist[crd] + edge[j]; //更新子结点的dist
                 q.push(make_pair(-dist[ne], ne)); //把新的二元组插入堆
            }
        }
    }
    return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 10000
int edge[MAX]; //储存边的值
int ver[MAX]; //代表有向边出发的结点
int son[MAX]; //代表有向边指向的结点
/*
注意这里ver和son的含义改变了
ver存的是一条边的起点下标
son存的是一条边的终点下标
请读者自己更改添加边函数
*/
int dist[MAX]; //最短路
int tot = 0; // 边的数量
using namespace std;
void BellmonFord()
{
    memset(dist, 0x3f, sizeof(dist)); //初始化dist
    dist[1] = 0; //设置起点
    //循环N – 1次，因为无负环的最短路步数最多为N – 1
    for(int i = 1; i < N; i++)
    {
        //遍历tot条边，找到指向结点dist最小的边
        for(int j = 1; j <= tot; j++)
        {
            if(dist[ver[j]] + edge[j] < dist[son[j]])
            {
                dist[son[j]] = dist[ver[j]] + edge[j];
            }
        }
    }
    return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#define MAX 10000
int head[MAX]; //代表一个结点，也是子结点链的起点
int edge[MAX]; //储存边的值
int son[MAX]; //子结点链
int ver[MAX]; //代表有向边
int dist[MAX]; //最短路
bool tag[MAX]; //标记结点
int tot = 0; //边的数量
int N;
using namespace std;
void BellmonFord()
{
    memset(dist, 0x3f, sizeof(dist)); //初始化dist
    dist[1] = 0; //设置起点
    queue<int> q; //定义队列，存储可能改变的结点
    q.push(1); //把起点添加进队列
    tag[1] = true; //打上标记
    while (!q.empty()) //一直循环，直到队列为空
    {
        int crd = q.front(); //从队列中取一个结点
        q.pop(); //移出队列
        tag[crd] = false; //去掉标记
        //遍历连接crd的子节点
        for(int j = head[crd]; j; j = son[j])
        {
            int ne = ver[j];
            if(dist[crd] + edge[j] < dist[ne])
            {
                dist[ne] = dist[crd] + edge[j];
                if(!tag[ne]) //如果子节点并不在队列中
                {
                    q.push(ne); //加入队列
                    tag[ne] = true; //打上标记
                }
            }
        }
    }
    return;
}

1
2
3
4
5
6
7
8
9
10
11

int dist[100][100]; //初始化dist数组
for (int k = 0; k < v; k++)
{
    for (int i = 0; i < v; i++)
    {
        for (int j = 0; j < v; j++)
        {
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}