第一节 只有五行的算法Floyd算法
问题：求任意两个城市之间的最短路径？多源最短路径。
解法1:O(n ²)的深度或广度遍历优先搜索
解法2:Floyd，O(n³)
Floyd 算法：从i号点到j 号点最多经过k个点的最短路径。--一种动态规划的思想
可以处理边的值为负数的图，但不能处理有负权回路的图。
核心是五行代码
答案：
map = [
nil,
[nil, 0, 2, 6, 4],
[nil, 999, 0, 3, 999],
[nil, 7, 999, 0, 1],
[nil, 5, 999, 12, 0]
]
# floyd核心5行 ,从i到j的最短路程
i = j = k = 1
for k in 1..4 do
for i in 1..4 do
for j in 1..4 do
if map[i][j] > map[i][k] + map[k][j]
map[i][j] = map[i][k] + map[k][j]
end
end
end
end
# 输出结果
for i in 1..4 do
for j in 1..4 do
printf("%4d",map[i][j])
end
print "
"
end
第2节 Dijkstra算法--单源最短路径
基本思想：每轮找到离起源点最近的一个点，然后以该点为中心进行扩散，通过该点相邻边的“松弛”，得到起源点到其余各点的估计路程，如此反复循环最终得到起源点到其余所有点的最短路径。
时间复杂度 O(n ²),不能解决负权边的问题。
边数远小于n ²的图称为稀疏图，可以用邻接表代替邻接矩阵是时间复杂度优化（邻接表暂时没学会。）
过程：
- 将所有点分为两部分，已知最短路径集合P，未知最短路径的集合Q。最开始P中只有起源点一个点。用book数组记录，索引代表各点，如果值为1则代表在P中，如果值为0代表在Q中。
- 用dis数组记录起源点到其余各点的初始路径。自己到自己dis[start] = 0, 和起源点直接相连的点i，dis[i]=map[start][i],同时把不直接相连的点的路径设为无穷∞。999
- 在Q中的所有点中选择距离起源点start最近的点u（dis[u]最小），加入到集合P中。
- 考察u的所有出边，对每条边松弛操作。例如存在u->v的边，那么start->v的距离是dis[u] + map[u][v]. 用这个距离和dis[v]比较。存较小的值到dis[v]中。
- 重复以上步骤，直到Q为空，算法结束。最终dis中的值就是起源点到所有其他点的最短路径。
map = [
nil,
[nil, 0, 1, 12, 999, 999, 999],
[nil, 999, 0, 9, 3, 999, 999],
[nil, 999, 999, 0, 999, 5, 999],
[nil, 999, 999, 4, 0, 13, 15],
[nil, 999, 999, 999, 999, 0, 4],
[nil, 999, 999, 999, 999, 999, 0]
]
# 初始化dis数组，记录start起源点到其余各点的初始路程
dis = [nil]
print "输入起源点
"
start = gets.to_i
i= 1
for i in 1..6 do
dis[i] = map[start][i] #这里起源点是start
end
p "初始化dis:#{dis},起源点是#{start}"
# book初始化，用于记录已知最短路径的顶点集合,用1表示已知，0表示未知。
book = [nil]
for i in 1..6 do
book[i] = 0
end
book[start] = 1
###################Dijkstra算法核心
n = 6 #6个点
# 第6点无出边，所以是n -1 次循环,否侧改为n
i = 1
while i <= n -1
print "第#{i}次外循环：#{dis}
"
# 找到离起源点最近的点
min = 999999
j = 1
while j <= n
if book[j] == 0 && dis[j] < min
min = dis[j]
# u点为离起源点最近的点。
u = j
end
j += 1
end
# 标记放入已知最短路径集合
book[u] = 1
# 对u的所有出边连接的点v，进行松弛操作
v = 1
while v <= n
# 判断u和v是否相连
if map[u][v] < 999
# 判断是否是更近的路线，如果是更新dis[v]
if dis[v] > dis[u] + map[u][v]
dis[v] = dis[u] + map[u][v]
end
end
v += 1
end
i += 1
end
p "单源点#{start}到其余各点的最短路径:"
i = 1
for i in 1..6 do
p "#{start}到#{i}的最短路径是#{dis[i]}"
end
第三节 bellman-ford --可以解决负边的问题。
储存数据用邻接表，a,b,r三个数组，索引值代表每条边的数据，值储存a点，b点，和a->b的权值。
dis数组，储存起始点到其他点的权重。初始化为[0, 999，999，999，999。。。]
如第i条边储存在a[i]->b[i],权值r[i].
核心代码：
for k in 1..n-1 do
for i in 1..m do
if dis[[b[i]]] > dis[a[i]] + r[i]
dis[[b[i]]] = dis[a[i]] + r[i]
end
end
end
主要思想：求单源点到其他点的最短路径。这里是用边来松弛。第一轮得到起源点只通过1条边到其他点的最短路径，第2轮是起源点最多经过2条边到其他点的最短路径。。。第k轮，起源点最多经过k条边到达其余各点的最短路径。总共n-1轮。（起源点1各，其他点n-1个，任意两地之间的最短边至多n-1个）
一句话，对所有边进行n-1次松弛。
a = [nil,2, 1, 1, 4, 3]
b = [nil,3, 2, 5, 5, 4]
r = [nil,2, -3, 5, 2, 3]
# 初始化dis
dis = []
i = 1
for i in 1..n do
dis[i] = 999
end
# 设置1号点，
dis[1] = 0
p dis
# 核心算法,起始点经过k条边到达其他各点的最短路径dis[i]
i = k = 1
for k in 1..n-1 do
for i in 1..m do
if dis[b[i]] > dis[a[i]] + r[i]
dis[b[i]] = dis[a[i]] + r[i]
end
end
end
# 结果
p dis #=> [nil, 0, -3, -1, 2, 4]
判断是否有负权回路：再对所有边进行一次松弛，看看是否可以成功。
回路权值之和为正，正权回路。
回路权值值和为负，负权回路。
用check变量来检查变化，如果没有变化可以提前终止循环。
n = 5 #点
m = 5 #边
a = [nil,2, 1, 1, 4, 3]
b = [nil,3, 2, 5, 5, 4]
r = [nil,2, -3, 5, 2, 3]
# 初始化dis
dis = []
i = 1
for i in 1..n do
dis[i] = 999
end
# 设置1号点，
dis[1] = 0
p dis
# 核心算法,起始点经过k条边到达其他各点的最短路径dis[i]
i = k = 1
for k in 1..n-1 do
# 用check审查每轮松驰是否更新
check = 0
for i in 1..m do
if dis[b[i]] > dis[a[i]] + r[i]
dis[b[i]] = dis[a[i]] + r[i]
check = 1
end
end
# 如果没有更新dis ,则提前退出循环，算法结束。
if check == 0
break
end
end
# 再进行一轮松弛，如果发生变化，则有负权回路。
flag = 0
i = 1
for i in 1..m do
if dis[b[i]] > dis[a[i]] + r[i]
flag = 1
end
end
if flag == 1
print "此图有负权回路"
else
# 输出结果
p dis
end
第四节 bellman的优化算法。
优化目标： 仅对最短路径估计值发生变化的顶点的所有出边进行松弛操作。
dis = [nil, 0 , 999,999,999,999]
使用队列queue,存储这些顶点。
（使用邻接表简化）
用队列优化的关键：只有那些在前一遍松弛中改变了最短路径估计值的顶点，才可能引起它们邻接点最短路径估计值发生变化。所以，用一个queue来储存被成功松弛的顶点，之后只对队列中的点进行松弛的判断和处理，这就降低了算法的时间复杂度，最多O(n*m)
已经确定了最短路径的点就不需要再做一遍松弛了。实际上轮数会小于n
总结：开始时将源点加入queue。每次从队首（head）取出一个顶点，并对与其相邻的所有顶点进行松弛尝试，如果某个相邻点松弛成功，并且这个相邻点不在queue中（不在head和tail之间），则将它加入队列尾(然后tail+=1)。对当前顶点处理完毕后立即出队（head +=1）
，并对下一个新队首如上操作,直到队列为空时（head==tail）算法结束。
n = 5 #点
m = 7 #边
a = [nil,1, 1, 2, 2, 3, 4, 5]
b = [nil,2, 5, 3, 5, 4, 5, 3]
r = [nil,2, 10, 3, 7, 4, 5, 6]
# 初始化dis数组
# 初始化book，用来标记,默认0，刚开始都不在队列中
dis =[nil]
book=[nil]
i = 1
for i in 1..n do
dis[i] = 999
book[i] = 0
end
dis[1] = 0 # 求第一个点到其他点的最短路径
# 初始化first数组索引1～n的值为-1，表示顶点1～n暂时没有边被读入。
# first数组记录了每个点最后存入的邻接边的编号。如果一个点没有邻接边默认为-1
# before储存了所有的初始编号-1和first中没有储存的边的编号。
# before + first 储存了所有边号和初始编号-1# before[i]储存了“编号为i的边”的“出点a”的"上一条邻接边"的编号。这里i是出点a的最后读入的邻接边。
first = [nil]
before = [nil]
i = 1
for i in 1..n do
first[i] = -1
end
i = 1
for i in 1..m do
# 读入每条边，邻接表的关键代码：
before[i] = first[a[i]]
first[a[i]] = i
end
# 队列queue,用来记录点，这个点的出边可以执行松弛操作，即最短路径发生了变化
queue = [nil]
head = tail = 1
# 1号点入列
queue[head] = 1
tail += 1
while head < tail
# 处理的队首点
# k是边的编号。
# 下行代码是当前队列的head指向的顶点在first数组中的最后写入的相邻边的编号
k = first[queue[head]]
while k != -1
if dis[b[k]] > dis[a[k]] + r[k]
# 松弛成功，则更新顶点1到顶点b[k]的路径
dis[b[k]] = dis[a[k]] + r[k]
# book判断b[k]点是否在队列中
if book[b[k]] == 0 #不在队列
queue[tail] = b[k]
tail += 1
book[b[k]] = 1 #表示b[k]已经入队
end
end
# before[k]储存了“编号为k的边”的“出点a”的"上一条邻接边"的编号。 k = before[k]
#为了循环再赋值给k变量。直到满足退出循环的条件k = -1，这时head指向的点的所有邻接边都进行过了松弛操作。
end
p dis
# 出队
book[queue[head]] = 0
head += 1
end
p dis