源码:

单源最短路径

by pascal

在图论中,单源最短路径可以说是打开OI图论大门的黎明前夕,是一个快速认识图论的问题。单源最短路径有很多解法,在国内著名的就是SPFA,SPFA可以说是通俗易懂,又经济实惠。在此,献上最快的方法:Dijkstar。

图论认识基础

首先,我们要认识图是什么。

图其实就是有点和线连接的东西,边有边权,不管是值还是流量还是什么,就是一个值。

然后就是有向图和无向图的区分,有向图有特点的方向,不能反过来,而无向图的边就是双行道。(注意链式前向星无向图的存边方式是add(x,y,sum),add(y,x,sum))

其次,我们认识一下存图的方式,对于我来说,就是这两种:

1
2
1.邻接矩阵
2.链式前向星

所谓邻接矩阵其实就是二维存图,列一个表格这样子。输入 x,y,sum ,然后 table[x,y]:=sum 就可以了。优点是善于理解,操纵,而且反边呀什么的很方便。不过对于强大的数据来说,邻接矩阵就是一个梗,无论是时间复杂度还是空间复杂度都会炸上天。

邻接矩阵应用:

1
2
3
4
5
6
7
1.存图:
table[x,y]:=sum;
2.找到x到y的连边的值:
table[x,y]
3.找到x的所有连边的值
for i:=1 to 点数 do
	table[x,y]

链式前向星的优点是很多的,包括了时间复杂度和空间复杂度的大大增强。不过这个结构比较难理解,我就来细细的讲一下。

1
2
3
4
5
6
7
8
9
10
定义4个数组: reach[i] value[i] next[i] cnt[x]
(注意到一个细节 cnt 大括号里面的是x而不是i)

我们给每一条边的编号,按输入的顺序依次给出号码:1,2,3,4······
reach[i]代表第i个边到的是哪里。
value[i]代表第i个边的边权是多少。
而next[i]代表的则是上一个的起点为x的边的编号是几。(这相当于是一个链表)
(也很显然,如果这条边是x的第一条边,那么next[i]=-1。)
cnt[x]就是说起点为x的最后一条边的编号是几。
(这样子我们就做到了有头(-1)有尾(cnt[x]),这样子形成一个链表串连起来。)

如果还不理解,那么可以告诉你们一个很容易理解的一句话:链式前向星不能一次性调用x到y的值,只能把x的所有连边扫一遍。而这就是链式前向星的缺点,但是图论算法一般不会强制调用x,y的值,所有链式前向星可谓是绝顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
最后讲一讲链式前向星的调用方式:
i:=cnt[x]; (i是边的编号)
while i<>-1 (全部边的遍历了) do
begin
	操作:reach[i]是y,value[i]是边权
    i:=next[i]; 下一个边的编号
end;

一个小技巧,如果是无向图,我想知道反边的值是多少怎么办?

value[i]是x到y
value[i xor 1]是y到x
自己思考

单源最短路径概念及求法

概念都懂,起点x,终点y,边权sum。那么接下来讲一下2个方法:

SPFA

这个很多人知道,直接可以翻阅题解。

Dijkstra

先借阅这篇博客

这就浅显易懂了,找最小权值的连边,然后将新的点加入集合,把新的点的连接的边的所有边权和以前集合中的点的点的连接的点的边的边权再融为一个集合,那么下次寻找的时候就找出边的集合的最小值取出来,然后两边,然后继续。

注意,图论算法包括Prim在内可以优化的尽量优化(就像HLPP),所以这里建议大家还是打上heap优化来找最小值,速度很快。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//博客里面讲的很清楚了,我就不加太多注释
// luogu-judger-enable-o2
Uses math;

var
        long,cnt:array[0..10010] of longint;
        ask:array[0..10010] of boolean;
        value,reach,next,heap,node:array[0..500010] of longint;
        n,m,start,head,tail,num:longint;

procedure insert(x:longint);
var
        t,father:longint;
begin
        if x=1 then
                exit;
        father:=x div 2;
        if heap[father]>heap[x] then
        begin
                t:=heap[x];
                heap[x]:=heap[father];
                heap[father]:=t;
                t:=node[x];
                node[x]:=node[father];
                node[father]:=t;
                insert(father);
        end;
end;

procedure down(x:longint);
var
        son:longint;
        t:longint;
begin
        if x*2>num then
                exit;
        son:=x*2;
        if (son+1<=num)and(heap[son+1]<=heap[son]) then
                inc(son);
        if (heap[x]>heap[son]) then
        begin
                t:=heap[x];
                heap[x]:=heap[son];
                heap[son]:=t;
                t:=node[x];
                node[x]:=node[son];
                node[son]:=t;
        end;
        down(son);
end;

procedure read_;
var
        i,l,r,sum:longint;
begin
        filldword(cnt,sizeof(cnt) div 4,maxlongint*2+1);
        filldword(long,sizeof(long) div 4,maxlongint);

        read(n,m,start);
        for i:=1 to m do
        begin
                read(l,r,sum);
                reach[i]:=r;
                value[i]:=sum;
                next[i]:=cnt[l];
                cnt[l]:=i;
        end;

        long[start]:=0;
end;

procedure Dijkstar;
var
        i,node_,minlong,keynode:longint;
begin
        node_:=0;
        for i:=1 to n do
        begin
                inc(num);
                node[num]:=i;
                heap[num]:=long[i];
                insert(num);
        end;

        repeat
                minlong:=heap[1];
                keynode:=node[1];

                heap[1]:=heap[num];
                node[1]:=node[num];
                dec(num);
                down(1);

                if ask[keynode]=False then
                begin
                        inc(node_);
                        ask[keynode]:=True;
                        i:=cnt[keynode];
                        while i<>-1 do
                        begin
                                if long[reach[i]]>value[i]+long[keynode] then
                                begin
                                        long[reach[i]]:=value[i]+long[keynode];

                                        inc(num);
                                        heap[num]:=long[reach[i]];
                                        node[num]:=reach[i];
                                        insert(num);
                                end;
                                i:=next[i];
                        end;
                end;
        until node_=n;
        for i:=1 to n do
                write(long[i],' ');
end;

begin
        Read_;
        Dijkstar;
end.

For OI