第24章-单源最短路径

发表于 2021-11-30 更新于 2024-04-12 分类于算法阅读次数：本文字数： 967 阅读时长 ≈ 4 分钟

单源最短路径

环路

前驱结点

前驱子图

松弛操作

松弛（relaxation）技术：对于每个结点$v$来说，我们维持一个属性$v.d$，用来记录从源结点$s$到结点$v$的最短路径权重的上界。我们称$v.d$为s到$v$的最短路径估计

最短路径估计和前驱结点进行初始化:

INITIALIZE-SINGLE-SOURCE(G, s):
	for each vertex v in G.V
		v.d = infty 
		v.pi = NIL 
	s.d = 0

对一条边（$u$, $v$）的松弛过程:

测试是否可以对$s$到$v$的最短距离进行改善
- 将$s$到$u$的最短路径，加上结点$u$到$v$的权重,与当前$s$到$v$的最短距离进行比较
- 如果前者更小，则更新$v.d$和$v.\pi$

RELAX(u, v, w):
	if v.d > u.d + w(u, v):
		v.d = u.d + w(u, v)
		v.pi = u

其中 w(u, v)表示：点u到点v的权重 v.d: 表示从源s到v的最短距离 v.pi: 表示v的上一个节点

松弛操作和最短路径的性质

三角不等式性质
上界性质
非路径性质
收敛性质
路径松弛性质
前驱子图性质

Bellman-Ford算法

边的权重可以为负值

给定带权重的有向图$G=(V, E)$和权重函数$w: E\rightarrow R$

算法返回一个布尔值

如果存在权重为负值的环路，返回false（负值的环路，不停的循环，可以使总权重一直降低）
反之，给出最短路径和他们的权重

BELLMAN-FORD(G, w, s):
	INITIALIZE-SINGLE-SOURCE(G, s)
	for i=1 to |G.V| - 1
		for each edge(u, v) in G.E
			RELAX(u, v)
	for each edge(u, v) in G.E
		if u.d > v.d + w(u, v):
			return False
	return True

有向无环图中的单源最短路径问题

Dijkstra算法

差分约束和最短路径

最短路径的证明

练习

24.1-1

在图24-4中运行Bellman-Ford算法,使用结点$z$作为源结点。在每一遍松弛过程中以图中相同的次序对每条边进行松弛，给出每遍松弛操作后的$d$值和$\pi$值。然后，把边$(z, x)$的权重改为4，再次运行该算法，这次使用$s$作为结点。

使用$z$作为源节点：

$d$的值:

松弛次数	$s$	$t$	$x$	$y$
0	$\infty$	$\infty$	$\infty$	$\infty$
1	2	$\infty$	7	$\infty$
2	2	5	7	9
3	2	5	6	9
4	2	4	6	9

$\pi$的值：

$s$	$t$	$x$	$y$	$z$
NIL	NIL	NIL	NIL	NIL
$z$	NIL	$x$	NIL	NIL
$z$	$x$	$x$	$s$	NIL
$z$	$x$	$y$	$s$	NIL
$z$	$x$	$y$	$s$	NIL

修改权重之后

24.1-2

证明推论24.3

证明:

24.1-3

给定$G=(V, E)$是一个带权重且没有权重为负值的环路的有向图，对于所有结点$v\in V$，从源结点$s$到结点$v$之间的最短路径中，包含边的条数的最大值为$m$。（这里，判断最短路径的根据是权重，不是边的条数。）请对算法BELLMAN-FORD进行简单修改，可以让其在$m+1$遍松弛操作之后种植，即使$m$不是事先知道的一个值。

24.1-4

修改BELLMAN-FORD算法，使其对于所有结点v来说，如果从源节点$s$到结点$v$的一条路径上存在权重为负值的环路，则将$v.d$的值设置为$-\infty$

24.1-5

设$G=(V, E)$为一个带权重的有向图，其权重函数为$w: E \rightarrow R$。请给出一个时间复杂度为$O(VE)$的算法，对于每个结点$v \in V$，计算出数值$^*(v) = {(u, v)} $

24.1-6

假定$G=(V, E)$为一个带权重的有向图，并且图中存在一个权重为负值的环路。给出与i个有限的算法来列出所有该环路上的结点。请证明算法的正确性。

思考题

算法导论

发表于 2021-11-30 更新于 2024-04-12 分类于算法阅读次数：本文字数： 406 阅读时长 ≈ 1 分钟

算法导论

goroutine编程题

发表于 2021-11-22 更新于 2024-04-12 分类于算法阅读次数：本文字数： 400 阅读时长 ≈ 1 分钟

题目

创建10个goroutine,id分别是0,1,2,3...9

每个goroutine只能打印最后一位是自己id号的数字，例如: 3号只能打印3, 13, 23, 33...

编写一个程序，依次打印1-10000

第一想法是全局锁，如果只用一个锁，那就是10个goroutine一起抢锁，10个协程加10个锁的话,还要交替解锁。所以选择用channel，goroutine交替向下个管道发送消息。

读取空的channel会根据channel类型返回空的数据，所以需要判断channel读取是否成功，i, ok <- c,判断ok的值

我的解答

解析题目，10个goroutine，但是需要依次打印1-10000，

import (
	"fmt"
	"time"
)


var IsRunning = true

func print(gid int, m map[int]chan int) {
	curChan := m[gid]
	nextChan := m[(gid+1)%10]
	for IsRunning {
		select {
		case i, ok := <-curChan:
			if ok {
				fmt.Println(fmt.Sprintf("%d   goroutine id=%d", i, gid))
				i++
				if i > 10000 {
					IsRunning = false
				} else {
					nextChan <- i
				}
			}
		}
	}

}

func printInOrder() {

	memo := map[int]chan int{}
	for i := 0; i < 10; i++ {
		c := make(chan int, 1)
		memo[i] = c
	}
	fmt.Printf("%#+v\n", memo)

	for i := 0; i < 10; i++ {
		go print(i, memo)
	}
	firstChan := memo[0]
	firstChan <- 0
	for IsRunning {
		// time.Sleep(time.Millisecond)
	}
	defer func() {
		for k, c := range memo {
			fmt.Printf("关闭: %d\n", k)
			close(c)
		}
	}()
}

func main() {
	start := time.Now()
	printInOrder()
	fmt.Printf("用时: %s", time.Since(start))
}

# 输出:
9976   goroutine id=6
9977   goroutine id=7
9978   goroutine id=8
9979   goroutine id=9
9980   goroutine id=0
9981   goroutine id=1
9982   goroutine id=2
9983   goroutine id=3
9984   goroutine id=4
9985   goroutine id=5
9986   goroutine id=6
9987   goroutine id=7
9988   goroutine id=8
9989   goroutine id=9
9990   goroutine id=0
9991   goroutine id=1
9992   goroutine id=2
9993   goroutine id=3
9994   goroutine id=4
9995   goroutine id=5
9996   goroutine id=6
9997   goroutine id=7
9998   goroutine id=8
9999   goroutine id=9
10000   goroutine id=0
用时: 392.8411ms

python弱引用

发表于 2021-11-19 更新于 2024-04-12 分类于 Python 阅读次数：本文字数： 358 阅读时长 ≈ 1 分钟

python弱引用

阅读全文 »

图解TCP/IP-第五章IP协议相关技术

发表于 2021-11-06 更新于 2024-04-12 分类于网络阅读次数：本文字数： 193 阅读时长 ≈ 1 分钟

仅凭IP无法完成通信

DNS（Domain Name System）

IP地址不便记忆

DNS的产生

域名的构成

DNS查询

DNS如同互联网中的分布式数据库

ARP(Address Resolution Protocol)

ARP是一种解决地址问题的协议。以目标IP地址为线索，用来定位下一个应该接受数据分包的网络设备对应的MAC地址。

不能用于IPv6

ICMP

DHCP（Dynamic Host Configuration Protocol）

自动设置IP地址、同一管理IP地址分配。

NAT（Network Address Translator）

是用于在本地网络中使用私有地址，在连接互联网时转而使用全局IP地址的技术

IP隧道

其他IP相关技术

图解TCP/IP-第四章IP协议

发表于 2021-11-04 更新于 2024-04-12 分类于网络阅读次数：本文字数： 39 阅读时长 ≈ 1 分钟

IP即网际协议

IP基础知识

IP地址的基础知识

路由控制

IP分割处理与再构成

IPv6

IPv4首部

IPv6首部

图解TCP/IP-第三章数据链路

发表于 2021-11-03 更新于 2024-04-12 分类于网络阅读次数：本文字数： 926 阅读时长 ≈ 3 分钟

数据链路的作用

数据链路可以视为网络传输的最小单位

将信号与二进制0、1的转换是物理层的责任

数据链路层处理的数据也不是单纯的0、1的序列，该层把他们集合为一个叫做“帧”的块，再进行传输

数据链路相关技术:

MAC寻址（物理寻址）
介质共享
非公有网络
分组交换
环路检测
VLAN（virtual local area network，虚拟局域网络）

传输方式：

以太网
WLAN（wireless local area network，无线局域网）
PPP（point to point protocol，点对点通信协议）

阅读全文 »

高性能mysql学习笔记-第1章-mysql架构与历史

发表于 2021-10-25 更新于 2024-04-12 分类于数据库阅读次数：本文字数： 1k 阅读时长 ≈ 4 分钟

高性能mysql

阅读全文 »

图解TCP/IP-第一章网络基础

发表于 2021-10-24 更新于 2024-04-12 分类于网络阅读次数：本文字数： 435 阅读时长 ≈ 2 分钟

4层网络OSI模型

7层OSI模型：

应用层(Application Layer)

HTTP, HTTPS, FTP,Telnet, SSH, SMTP, POP3等
表示层(Presentation Layer)

把数据转化为能与接收者的系统割视兼容并适合传输的格式
会话层(Session Layer)

负责在数据传输中设置和维护计算机网络中两台计算机之间的通信连接
传输层(Transport Layer)

把传输表头(TH)加至数据形成数据包。传输表头包含了所使用的协议等发送信息。例如：传输控制协议（TCP）等
网络层(Network Layer)

决定数据的路径选择和转寄，将网络表头(NH)加至数据包，以形成分组。网络表头包含了网络资料。例如：互联网协议（IP）等
数据链路层(Data Link Layer)

负责网络寻址、错误侦测和改错。当表头和表尾被加至数据包时，会形成信息框（Data Frame 数据帧)。数据链表头（DLH）是包含了物理地址和错误侦测以及改错的方法。数据链表尾（DLT）是一串指示数据包末端的字符串。例如以太网、无线局域网（Wi-Fi）和通用分组无线服务（GTRS）等

分为两个子层：逻辑链路控制（logical link control, LLC）子层和介质访问控制（Media access control, MAC）子层
物理层(Physical Layer)

在局部局域网上发送数据帧(Data Frame)，它负责管理电脑通信设备和网络媒体之间的互通。包括了针脚、电压、线缆规范、集线器、中继器、网卡、主机接口卡等。

阅读全文 »

centos分区挂载

发表于 2021-10-20 更新于 2024-04-12 分类于系统阅读次数：本文字数： 72 阅读时长 ≈ 1 分钟

CentOS 7 增加磁盘分区挂载

阅读全文 »

松弛次数	\(s\)	\(t\)	\(x\)	\(y\)
0	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)
1	2	\(\infty\)	7	\(\infty\)
2	2	5	7	9
3	2	5	6	9
4	2	4	6	9

\(s\)	\(t\)	\(x\)	\(y\)	\(z\)
NIL	NIL	NIL	NIL	NIL
\(z\)	NIL	\(x\)	NIL	NIL
\(z\)	\(x\)	\(x\)	\(s\)	NIL
\(z\)	\(x\)	\(y\)	\(s\)	NIL
\(z\)	\(x\)	\(y\)	\(s\)	NIL