最短路问题与标号算法(label correcting algorithm)研究(5)
最短路问题与标号算法(label correcting algorithm)研究(5)
前文回顾
这是全文第三章label correcting algorithm的第三节。本章围绕Label Correcting Algorithms展开。前两节我们介绍了最短路径算法Generic Label Correcting Algorithm，Modified Label Correcting Algorithm，以及在前两个算法上改进得到的FIFO Label Correcting Algorithm，Deque Label Correcting Algorithm。以上四种算法都是单源最短路径算法，本小节我们将研究简单网络的多源最短路径问题以及对应的Floyd-Warshall Algorithm。点击下方链接回顾往期内容：
最短路问题与标号算法(label setting algorithm)研究(1) - 开篇介绍
最短路问题与标号算法(label correcting algorithm)研究(2) - 最短路径问题简介
最短路问题与标号算法(label correcting algorithm)研究(3)
最短路问题与标号算法(label correcting algorithm)研究(4)
3.6 多源最短路径算法
在前边介绍中我们主要考虑简单网络的单源最短路径问题，本小节我们将研究简单网络的多源最短路径问题，也就是说我们要找的是简单网络中任意两个节点之间的最短路径。为了实现这个目的，需要该网络中至少包含一条从任意节点到任意节点的有向路径，即网络具有强连接性(网络中任意两节点都是可达的)。如果网络不满足这个条件，我们可以通过增加一条弧长为无穷大的虚拟弧来解决。
这里我们将介绍两种求解简单网络多源最短路径的Label Correcting Algorithms，第一种算法是基于之前所介绍的单源Label Correcting Algorithms实现的，简单来说就是依次将网络中的每个节点作为源节点，求解它到其他节点的最短路径，我们称其为Repeated Shortest Path Algorithm；第二种算法是基于多源最短路径最优性条件实现的算法，我们称其为All-pairs Label Correcting Algorithm，这种算法其实是Label Correcting Algorithms的普适化，可以将单源Label Correcting Algorithms看作All-pairs Label Correcting Algorithm的特例。第一种方法较为简单这里不再赘述。
我们将在3.6.1小节给出多源最短路径最优性判别条件；以多源最短路径最优性条件为基础，3.6.2小节介绍了All-pairs Generic Label Correcting Algorithm的一般步骤，并对其可行性进行说明；3.6.3小节对All-pairs Generic Label Correcting Algorithm中的经典算法——Floyd-Warshall Algorithm做进一步介绍。
3.6.1 多源最短路最优性条件
在All-pairs Label Correcting Algorithm中我们记为任意节点对的距离标签，代表从节点到节点的一条路径的长度的上界。算法不断更新距离标签矩阵，直到所有的距离标签都为最短路径长度。其所依据的"全对最短路径最优性条件"如下：
最优性定理2：对于任意一对节点，记为节点到节点的有向路径长度，当且仅当满足以下条件时，为节点到节点的最短路径长度（6）：
证明过程可参考定理1，这里不再赘述。
3.6.2 All-Pairs Generic Label Correcting Algorithm
All-Pairs Generic Label Correcting Algorithm求解思想与单源Label Correcting Algorithms类似：从一些距离标签开始，不断对其更新直到其满足最优性条件。以下给出了All-pairs Generic Label-Correcting Algorithm的一般步骤：
表3-14 All-pairs Generic Label-Correcting Algorithm
接下来我们对该算法的收敛性和正确性进行证明。首先来看正确性：算法在每次迭代时，只要节点对的距离标签为有限值，就代表了一条从节点到节点的长度为的有向路径。当算法满足最优性条件结束迭代时，节点到节点的有向路径可分解为一些有向环和一条路径。由于我们所研究的网络中不含有环，所以路径的长度就等于有向路径的长度，又因为这条路径满足最优性条件，因此就是节点对的最短路径长度。接下来分析收敛性：由于所有的弧长均为整数，且最大的弧长为C，所以任意节点对的距离标签取值范围是。在每次迭代中算法不断减小距离标签的值，因此算法在内结束迭代。由此证明该算法的收敛性和正确性。
请注意表3-14第5行，在检查节点距离标签是否满足最优性条件2时并没有给出具体的检查规则。与generic label-correcting algorithm类似，不明确的检查规则会导致算法的求解效率无法得到保障。这里不再给出All-Pairs Generic Label Correcting Algorithm的相应代码实现。
3.4.1 Floyd-Warshall Algorithm
算法介绍
为了解决All-Pairs Generic Label Correcting Algorithm节点检查规则不明确带来的算法效率问题，这里给出Floyd-Warshall的改进方法。Floyd-Warshall基于动态规划技术对算法进行了改进，这就是著名的Floyd-Warshall Algorithm。其核心是在第k次迭代时只考虑将节点作为节点对的中间节点，具体做法如下：令为第k次迭代后节点对的距离标签，且在第k次迭代时只考虑将节点作为其内部节点。算法开始时，计算任意节点对的距离标签，然后依据最优性条件2更新任意节点对之间的距离标签，重复上述过程。最终即为节点对的最短路径长度。第k次迭代时更新规则如下（7）：
（公式可拖动）
Floyd-Warshall Algorithm关键步骤伪代码如下：
表3-15 Floyd-Warshall Algorithm
与单源最短路径算法不同，多源最短路径算法以记录节点对的前向节点。记录了当前路径中到达终点前的最后一个节点，当距离标签更新时也随之更新。当算法结束时，我们可以通过来生成从节点到节点的最短路径：假设生成从节点到节点的最短路径，首先令，把节点加入；然后令，把节点加入。重复上述过程直到。
复杂度分析
Floyd-Warshall Algorithm给出了明确的检查节点的顺序，使得算法迭代次数控制在，
算法实现
首先给出Python版本的Floyd-Warshall Algorithm实现（求解附录2中任意节点间的最短路径）
"""导入相关基础包，定义全局变量"""
import pandas as pd
import numpy as np
g_node_list=[] #网络节点集合
g_node_zone={} #网络节点类别集合
g_link_list=[] #网络弧集合
g_shortest_path=[]#最短路径集合
g_number_of_nodes=0#网络节点个数
node_predecessor=[]#前向节点集合
node_label_cost=[]#距离标签集合
Max_label_cost=99999#初始距离标签
"""导入网络数据文件，构建基础网络并初始化相关变量"""
#读取网络节点数据
df_node=pd.read_csv('./input_file/node.csv')
df_node=df_node.iloc[:,:].values
for i in range(len(df_node)):
g_node_list.append(df_node[i,0])
g_node_zone[df_node[i, 0]] = df_node[i, -1]
g_number_of_nodes+=1
node_label_cost=np.ones((g_number_of_nodes,g_number_of_nodes))\
*Max_label_cost
node_predecessor=np.zeros((g_number_of_nodes,g_number_of_nodes))
for i in range(g_number_of_nodes):
for j in range(g_number_of_nodes):
if i==j:
node_label_cost[i,j]=0
#读取网络弧数据
df_link=pd.read_csv('./input_file/road_link.csv')
df_link=df_link.iloc[:,:].values
for i in range(len(df_link)):
g_link_list.append((df_link[i,1],df_link[i,2]))
node_label_cost[df_link[i,1]-1,df_link[i,2]-1]=df_link[i,3]
node_predecessor[df_link[i,1]-1,df_link[i,2]-1]=df_link[i,1]
"""最短路径求解：扫描网络弧，依据检查最优性条件更新距离标签"""
for k in g_node_list:
for arc_head in g_node_list:
for arc_tail in g_node_list:
if node_label_cost[arc_head-1,arc_tail-1]>\
node_label_cost[arc_head-1,k-1]+node_label_cost[k-1,arc_tail-1]:
node_label_cost[arc_head-1,arc_tail-1]=\
node_label_cost[arc_head-1,k-1]+node_label_cost[k-1,arc_tail-1]
node_predecessor[arc_head-1,arc_tail-1]=\
node_predecessor[k-1,arc_tail-1]
"""依据前向节点生成最短路径"""
agent_id=1
for from_node in g_node_list:
o_zone_id=g_node_zone[from_node]
for to_node in g_node_list:
if from_node!=to_node:
d_zone_id=g_node_zone[to_node]
if node_label_cost[from_node-1,to_node-1]==Max_label_cost:
path =" "
else:
path="%s" % to_node
prior_point=\
int(node_predecessor[from_node-1,to_node-1])
while prior_point!=from_node:
path= "%s;" %prior_point+path
prior_point=\
int(node_predecessor[from_node-1,prior_point-1])
path="%s;" %from_node + path
g_shortest_path.append([agent_id, o_zone_id,d_zone_id, path,node_label_cost[from_node-1,to_node-1]])
"""将求解结果导出到csv文件"""
#将数据转换为DataFrame格式方便导出csv文件
g_shortest_path=np.array(g_shortest_path)
col=['agent_id','o_zone_id','d_zone_id','node_sequence','distance']
file_data = pd.DataFrame(g_shortest_path, index=range(len(g_shortest_path)),columns=col)
file_data.to_csv('./5_floyd_warshall/agent.csv', index=False)表3-16 Python实现Floyd-Warshall Algorithm（代码可拖动）
接下来给出MATLAB版本的Floyd-Warshall Algorithm实现（求解附录2中源节点1到其他节点的最短路径）。
%% clear
clc
clear
%% 设置变量
g_node_list=[]; %网络节点集合
g_link_list=[]; %网络弧集合
g_number_of_nodes=0; %网络节点个数
node_predecessor=[]; %前向节点集合
node_label_cost=[]; %距离标签集合
Max_label_cost=inf;%初始距离标签
%% 导入网络数据文件，构建基础网络并初始化相关变量
%读取网络节点数据
df_node = csvread('node.csv',1,0);
g_number_of_nodes = size(df_node,1);
g_node_list = df_node(:,1);
node_label_cost=ones(g_number_of_nodes,g_number_of_nodes)*…
Max_label_cost;
node_predecessor=zeros(g_number_of_nodes,g_number_of_nodes);
for i = 1 : g_number_of_nodes
for j = 1 : g_number_of_nodes
if i==j
node_label_cost(i,j)=0;
end
end
end
%读取网络弧数据
df_link = csvread('road_link.csv',1,0);
g_link_list = df_link(:,2:3);
for i = 1 : size(df_link,1)
Distance(df_link(i,2),df_link(i,3)) = df_link(i,4);
node_label_cost(df_link(i,2),df_link(i,3))=df_link(i,4);
node_predecessor(df_link(i,2),df_link(i,3))=df_link(i,2);
end
%% 最短路径求解：扫描网络弧，依据检查最优性条件更新距离标签
for k = 1 : g_number_of_nodes
for arc_head =1:g_number_of_nodes
for arc_tail =1:g_number_of_nodes
if node_label_cost(arc_head,arc_tail)>…
node_label_cost(arc_head,k)+node_label_cost(k,arc_tail)
node_label_cost(arc_head,arc_tail)=…
node_label_cost(arc_head,k)+node_label_cost(k,arc_tail);
node_predecessor(arc_head,arc_tail)=…
node_predecessor(k,arc_tail);
end
end
end
end
%% 依据前向节点生成最短路径
agent_id_column = [1:((g_number_of_nodes-1)*g_number_of_nodes)]';
o_zone_id_column = [];
d_zone_id_column = [];
path_column = {};
distance_column = [];
for from_node = 1 : g_number_of_nodes
for to_node = 1 : g_number_of_nodes
if from_node~=to_node
if node_label_cost(from_node,to_node)==Max_label_cost
path = "";
distance = 99999;
distance_column = [distance_column; 99999];
else
path=num2str(to_node);
prior_point=node_predecessor(from_node,to_node);
while prior_point~=from_node
path=strcat(';',path);
path=strcat(num2str(prior_point),path);
prior_point=node_predecessor(from_node,prior_point);
end
path=strcat(';',path);
path=strcat(num2str(from_node),path);
distance_column = [distance_column;…
node_label_cost(from_node,to_node)];
end
path_column=[path_column;path];
o_zone_id_column=[o_zone_id_column;df_node(from_node,5)];
d_zone_id_column=[d_zone_id_column;df_node(to_node,5)];
end
end
end
title = {'agent_id','o_zone_id','d_zone_id','node_sequence','distance'};
result_table=table(agent_id_column,o_zone_id_column,…
d_zone_id_column,path_column,distance_column,'VariableNames',title);
writetable(result_table, 'agent.csv',…
'Delimiter',',','QuoteStrings',true)表3-17 MATLAB实现Floyd-Warshall Algorithm（代码可拖动）
3.7 总结
在本章中，我们首先介绍了求解简单网络单源最短路径问题的Generic Label Correcting Algorithm的一般流程，随后基于不同的改进方法依次介绍了：Modified Label Correcting Algorithm、FIFO Label Correcting Algorithm、Deque Label Correcting Algorithm。其中，FIFO Label Correcting Algorithm和Deque Label Correcting Algorithm可以认为是Modified Label Correcting Algorithm的特殊实现。其次，对简单网络的多源对短路径问题进行了探讨，介绍了两种不同的求解思路：基于单源最短路径算法实现和基于All-Pairs Generic Label Correcting Algorithm实现，最后介绍了后者中的经典算法：Floyd-Warshall Algorithm。
从上面内容我们不难发现Label Correcting Algorithms是以路径最优性条件为前提展开的，Generic Label Correcting Algorithm（Modified Label Correcting Algorithm）为我们提供了基本算法框架，允许我们采用不同的规则对弧选择进行处理（对节点选择进行处理），这是Label Correcting Algorithms的优势，即我们可以根据实际需要灵活调整相应规则，使得算法具有很好的拓展性。同时这也是Label Correcting Algorithms的缺点，不合适的处理规则会降低算法的效率。在表3-18中我们对上述算法的特点进行了总结供读者在选择算法时加以参考。
表3-18 Label Correcting Algorithms