Xinyang's Blog

All-pairs shortest path algorithm

问题描述

给定图 ,其中 为点集, 为边集。 表示连接 两点之间的边的权重,如果两点间没有边则为

求任意两个顶点 之间最短路径的长度 dist[i][j]

算法思想

  • 首先我们考虑这样一个问题:找到一条长度尽可能短,并且跳转尽可能少的路径。具体来说,我们要求一个数组 dist[i][j][k],表示在 这两个结点之间,最多经过 个点的最短路径长度。

    显然,当 时,也就是不经过任何点时, 之间的距离等于他们之间的边权

    而当时,到达 的路径可以被所有与 相连的点更新,即

    $2
    i
    ux
    j
    u1
    u2
    ...

    图中

    1
    2
    3
    4
    5
    6
    dist[i][j] <- w[i][j]
    for k = 1 to |V|:
    for i in V:
    for j in V:
    for u in V:
    dist[i][j][k] <- min(dist[i][j][k-1], dist[i][u][k-1] + w[u][j])

    上面的算法怎么优化?

    • 滚动数组空间优化

      dist[i][j][k] <- dist[i][u][k-1] + w[u][j] new_dist[i][j] <- dist[i][u] + w[u][j]

    • 我们需要最外层循环吗?

      $2
      i
      p1
      j
      p2
      p3

      假设橙色为最短路,我们只执行一边上述循环的话,只能找到,找不到橙色的最短路。

      究其原因,是因为我们不能保证在更新dist[i][j]时,dist[i][ux]dist[ux][j]已经是最短的。那么如果我们按照一定的顺序更新dist数组,使得我在更新到dist[i][j]时,所有的 的前驱结点 dist[i][ux], dist[ux][j]已经更新好,那么我们是不是就不需要外层循环了呢?

    • 对比一下min(dist[i][j], dist[i][u] + w[u][j]) 和 矩阵乘法的内层:dist[i][j] + dist[i][u] * w[u][j]),发现它们有异曲同工之处

      矩阵乘法中,

      1
      2
      3
      4
      5
      for k = k * 2:
      for i in V:
      for j in V:
      for u in V:
      dist[i][j][k] <- min(dist[i][j][k / 2], dist[i][u][k / 2] + dist[u][j][k / 2])
  • 另一种解法

    一条最短路径 一定包含0个或者若干个中间点。

    如果我们选择点集 中前 个点 作为中间点,那么它有一条很好的性质:

    1. 如果 的最短路径中不包含 ,那么

      $2
      i
      u
      j
      p2
      p3

    2. 如果 的最短路径中包含 ,那么

      $2
      i
      p1
      j
      p2
      u
      u1
      $2
      i
      p1
      j
      p2
      u
      u1

    所以我们可以写出状态转移方程

举例说明

伪代码

1
2
3
4
5
6
7
8
9
10
Floyd-Warshall(G{V,E}):
for i = j:
dist[i][j] <- 0
for i != j
dist[i][j] <- w[i][j]
for k in V:
for i in V:
for j in V:
dist[i][j] <- min(dist[i][j], dist[i][k] + dist[k][j])
pre[i][j] <- pre[k][j] if dist[i][k] + dist[k][j] smaller

分析算法复杂度

  • 算法

    由于算法有3层循环,循环最内部复杂度为,所以复杂度为

  • 调用 算法

    • 没有堆优化

      1次:

      n次:

    • 加入堆优化

      1次:

      n次:

对比两种算法的时间复杂度, 算法在 的稀疏图上有一定优势。

但是, 算法能够处理含有负权边的情况,这一点优于 算法。

关于转义序列

问题引入

首先有这样一个有趣的问题

1
2
3
// escape.c
printf("??ab?c\t?dfrge\rf\tg\n");
printf("??ab?c\t?dfrge\rf\tg");

这两行代码分别应该输出什么呢?看到这道题的时候,我是懵逼的,因为\r \b这样的字符实在是很少使用。于是,我上机测试了一下。

1
2
3
### Environment: Windows 10 20H2, gcc, powershell ###
f gdfrge
f gdfrge
1
2
3
### Environment: Ubuntu 20.04, gcc, zsh ###
f?ab?c gdfrge
f?ab?c g

看到输出结果,我:???

这个输出主要有几个问题不好解释:

  1. 为什么不同环境下输出的结果不同?
  2. Ubuntu环境下,为什么第二条语句的输出没有后5个字符?
  3. 将字符串分为两个部分,\r之前和\r之后。按照dfrge的位置来计算,前一部分中的\t的宽度为2个字符,后一部分中\t的宽度为7个字符,\t的宽度是如何计算的?

转义序列

我们先来回顾一下书上所描述的一些转义序列:

Escape Sequences Meaning
\b Backspace.
\n Newline.
\r Carriage return.
\t Horizontal tab.
\v Vertical tab.
\a Alert (ANSI C).
\f Form feed.
C Primer Plus中的描述

我们分别来看一下这些转义序列:

\b 用来将光标向回移动一格,但是要注意的是,这里的移动光标并不等于我们敲击键盘上的退格键(Backspace),\b仅仅会移动光标,而回退的内容并不会被删除掉,接下来的内容会插入到光标后面,覆盖掉原有的内容。另外,在stdin中的输入也会覆盖光标后的字符。

1
2
3
4
5
6
7
8
9
printf("Hi there!\b, ");
printf("welcame!\b\b\b\bo\n");
printf("Please type your name: ____.\b\b\b\b");
scanf("%s",name);
----------------------------------------
Output:
Hi there, welcome!
//输入John
Please type your name: John.

\n \r 之所以将这两个字符放在一起,是因为在不同的系统中处理文件中“换行”的方式不同,因此这两个字符的含义没有一个统一标准。Windows使用Carrier Return(\r)来表示将光标置于行开头,用Line Feed(\n)来将光标移动到当前位置的正下方一行;Linux则直接使用(\n)来表示回车+换行。如果你想了解为什么有这样的区别,Stack Overflow联合创始人Jeff Atwood写的这篇文章十分清晰的阐释了这个问题。

不过对于命令行来说,似乎并没有这样的区别(具体原因未知,有待进一步测试)。

\t 用来将光标移动到下一个制表位(Tab stop)。假设你现有环境中制表符的宽度是w(在终端中,一般w = 8),光标所处位置是p,那么输出一个\t会将光标移动到第n*w位,其中n为一个整数,n*w >= p

1
2
3
4
5
6
printf("bbbbbbb\ta"); putchar('\n');
printf("bbbbbbbb\ta");
----------------------------------------
Output:
bbbbb a
bbbbbbbb a

\v 垂直制表符,基本上等同于\n\t一同作用的效果。据说出现的目的是为了加快打印机的打印速度(?)

\a 播放警示声音,这个控制符蛮有意思的,可以用来恶心用户提示用户

\f 用来告诉打印机强制跳转到下一页,不过在现代系统中好像并没有这样的功能


问题解释

1. 为什么不同环境下输出的结果不同?

本质上讲,转义序列只是一些字符,C只能将这些字符传入输出流中,至于如何处理,因流和系统环境的差异而有很多不同。

例如,上面的代码在Windows下运行,得到的结果并没有?ab?c,说明Windows处理”??ab?c\t?dfrge\rf\tg\n”中标重点的\t时,会选择用\t覆盖掉已经输出了的内容,即?ab?c。相反,在Ubuntu中并不会出现这样的现象,因为Ubuntu中的\t并不会覆盖已经输出的内容,而仅仅是将光标移动到下一个Tab stop。

2. Ubuntu环境下,为什么第二条语句的输出没有后5个字符?

Linux terminal似乎只会打印到所在行光标所在位置,对于光标后面的字符并不会打印。在Ubuntu上测试另外一个字符串:

1
2
3
4
printf("??ab?c\t?dfrge\rf\tg\t");
----------------------------------------
Output:
f?ab?c gdfrge

这一方面说明在Ubuntu上\t不会覆盖已经输出的字符,一方面说明终端只会输出光标之前的内容。

3. \t的宽度是如何计算的 ?

参考上一部分中关于制表位的描述。


ANSI转义序列

刚才还留下了一个问题,\f并不能实现强制换页。那么如果想实现强制换页的操作,应该怎么办呢?

ANSI转义序列(ANSI escape sequences)是一种带内信号转义序列标准,用于控制视频文本终端上的光标位置、颜色和其他选项。在文本中嵌入确定的字节序列,大部分以ESC转义字符和”[“字符开始,终端会把这些字节序列解释为相应的指令,而不是普通的字符编码

Wikipedia

ANSI转义序列能够实现更多功能,包括控制光标向上移动、控制输出字符的颜色、清屏等等。这里是一份完整的查询表,下面的例子中用到了一些常用的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//Environment: Ubuntu 20.04, gcc, zsh
//Not sure about whether this will work on windows.
//Windows 10 and windows terminal support ANSI escape sequence
//so if you are using them, this should work properly.
#include <stdio.h>
#include <unistd.h>

int main(){
printf("Hello, Welcome to this ANSI escape sequence test\n");
printf("\033[33mNow, we are printing in yellow\n");
printf("\033[4mYou can also underline sentences.\n");
printf("\033[0;31mBesides, you can print in red.\n");
printf("\033[0mHopefully, you understand what's happening.\n");
sleep(8);
printf("\033[0m\033[2J\033[H");
printf("\033[32mTry to input something,press CTRL-D to end input\n");
while(getchar() != EOF);
printf("\nYou see, text you typed in are green.");
return 0;
}

‘\033’在ASCII编码中是转义字符的意思,它标志着后面的东西的意思发生了变化。


Try Yourself

用转义字符实现进度条

这里写了一个简单的打印进度条的函数,通过循环调用来实现进度条的效果。

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
#include <stdio.h>
#include <unistd.h>

void PrintProgressBar(int progress, int interval, int theme){
//progress is a number in range [0,100] indicating the progress of a work.
//interval is the time waited between each function call. Count in seconds.
//theme is the choice of theme in which the progress bar is presented.
putchar('\r');
printf("\033[?25l");
static int in_frame = 0;
const int MAXWIDTH = 50;
const char frame[] = {'|','/','-','\\'};
const int FRAMELEN = 4;
int width = progress*MAXWIDTH/100;
switch (theme){
case 1:
// \ | / - and number in the end
printf("%c %d%%", frame[in_frame],progress);
in_frame = (in_frame + 1) % FRAMELEN;
break;

case 2:
putchar('[');
for(int i = 0; i < width; i++){
putchar('=');
}
putchar('>');
for(int i = width+1; i <= MAXWIDTH; i++){
putchar(' ');
}
putchar(']');
printf(" %d%%",progress);
default:
putchar('[');
for(int i = 0; i < width; i++){
putchar('=');
}
putchar('>');
for(int i = width+1; i <= MAXWIDTH; i++){
putchar(' ');
}
putchar(']');
printf(" %c %d%%", frame[in_frame],progress);
in_frame = (in_frame + 1) % 4;
}
printf("\033[K");
sleep(interval);
//Linux uses line buffer when printing in terminal,which means
//that you need to tell the terminal when to end the line
//by sending a newline character, printing enough content to fill up the buffer
//or getting an input.
//
//Since we are always on the same line printing short sentences,we satisify 0 of 3 conditions.
//There's no way that computer will print the content in buffer.
//so we need to use fflush whose function is
//telling the computer to print all characters in buffer.
fflush(stdout);
}


int main(){
for(int i = 1; i <= 100; i++){
PrintProgressBar(i,1,0);
}
printf("\033[?25h");
return 0;
}

跳舞的颜文字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main(){
const int syn_size = 2,TIME = 100;
char syn[][1000] = {"└|``┌|","|┐``|┘"};
printf("\033[?25l");
for(int T = 0; T < TIME; T++){
for (int i = 0; i < syn_size; i++){
printf("\r%s", syn[i]);
fflush(stdout);
sleep(1);

}
}
printf("\033[?25h");
return 0;
}