HAWQ + MADlib 玩转数据挖掘之（十）——图算法之单源最短路径
HAWQ + MADlib 玩转数据挖掘之（十）——图算法之单源最短路径
一、图算法简介
1. 定义
在计算中，常将运算方程或实验结果绘制成由若干有标尺的线条所组成的图，称为“算图”。计算时根据已知条件，从有关线段上一点开始，连结相关线段上的点，连线与表示所求量线段的交点即为答案。
无向图、有向图和网络能运用很多常用的图算法。这些算法包括：各种遍历算法（这些遍历类似于树的遍历），寻找最短路径的算法，寻找网络中最低代价路径的算法，用于回答一些简单相关问题例如，图是否是连通的，图中两个顶点间的最短路径是什么，等等。
2. 常用的图算法
（1）图的遍历
图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作是图的一种基本操作，图的许多操作都建立在遍历操作的基础之上。
在遍历图时，为保证图中各顶点在遍历的过程中访问且仅一次，需要为每个顶点设计一个访问标记，设置一个数组，用于标示图中每个顶点被访问过，它的初始值全部为0，表示顶点均未被访问过；某个顶点被访问后，将相应访问标志数组中的值设为1，以表示该顶点已经被访问过。
通常，图的遍历有两种：深度优先遍历搜索和广度优先遍历搜索。
（2）最小生成树
对于有n个顶点的无向连通图，至少有n-1条边，而生成树恰好有n-1条边，所以生成树是图的极小连通子图。如果无向连通图是一个网，那么它的所有生成树中必有一棵边的权值总和最小的生成树，称这颗生成树为最小生成树。
最小生成树可以用普里姆算法或克鲁斯卡尔算法求出。
（3）最短路径
- 从一个源点到其它各点的最短路径。求解单源最短路径的算法主要是Dijkstra算法和Bellman-Ford算法，其中Dijkstra算法主要解决所有边的权为非负的单源最短路径问题，而Bellman-Ford算法可以适用于更一般的问题，图中边的权值可以为负。
- 每一对顶点之间的最短路径，可使用弗洛伊德算法来求解。
二、单源最短路径
（1）问题描述
给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
（2）Bellman-Ford算法
Dijkstra算法无法判断含负权边的图的最短路。如果遇到负权，在没有负权回路（回路的权值和为负，即便有负权的边）存在时，也可以采用Bellman-Ford算法正确求出最短路径。
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=(V,E), 其源点为s，加权函数 w是 边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E)
算法描述：
- 初始化：将除源点外的所有顶点的最短距离估计值 d[v] ——>+∞, d[s]——>0;
- 迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最。短距离估计值逐步逼近其最短距离；（运行|v|-1次）
- 检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。
三、Madlib中的单源最短路径算法相关函数
1. 单源最短路径函数
该函数使用Bellman-Ford算法实现。
（1）语法
graph_sssp( vertex_table,
vertex_id,
edge_table,
edge_args,
source_vertex,
out_table
)（2）参数
vertex_table：TEXT类型，包含图中顶点数据的表名。
vertex_id：TEXT类型，缺省值为‘id’，vertex_table表中包含顶点的列名。顶点列必须是INTEGER类型，并且数据不能重复，但不要求连续。
edge_table：TEXT类型，包含边数据的表名。边表必须包含源顶点、目标顶点和边长三列。边表中允许出现回路，并且构成回路的权重可以不同。
edge_args：TEXT类型，是一个逗号分隔字符串，包含多个“name=value”形式的参数，支持的参数如下：
- src （INTEGER）：边表中包含源顶点的列名，缺省值为‘src’。
- dest （INTEGER）：边表中包含目标顶点的列名，缺省值为‘dest’。
- weight （FLOAT8）：边表中包含边长的列名，缺省值为‘weight’。
source_vertex：INTEGER类型，算法的起始顶点。此顶点必须在vertex_table表的vertex_id列中存在。
out_table：TEXT类型，存储单源最短路径的表名，表中的每一行对应一个vertex_table表中的顶点，具有以下列：
- vertex_id：目标顶点ID，使用vertex_id入参的值作为列名。
- weight：从源顶点到目标顶点最短路径的边长合计，使用weight入参的值作为列名。
- parent：在最短路径上，本顶点的上一节点，列名为‘parent’。
2. 路径检索函数
路径检索函数返回从源顶点到指定目标顶点的最短路径。
（1）语法
graph_sssp( sssp_table,
dest_vertex
)（2）参数
sssp_table：TEXT类型，单源最短路径函数的输出表名。
dest_vertex：INTEGER类型，指定目标顶点。
四、单源最短路径示例
单源最短路径问题是图算法的经典问题，在现实中有很多应用，比如在地图中找出两个点之间的最短距离、最小运费等。社交网络中出现的“六度人脉”功能，可以查看到一个用户和一个陌生人之间可以通过哪几个人认识，也就是所谓的六度关系。这个问题也可抽象为一个单源最短路径问题。将用户作为顶点，用户之间的好友关系作为边，“六度关系”就是两个用户之间的最短路径。在这个特殊场景下，所有边的权重都可认为是1。当然，如果用户量巨大，用户好友关系将变得非常复杂，单纯的最短路径算法可能存在性能问题，需要进行改进与优化。
1. 建立表示图的顶点表和边表
drop table if exists vertex, edge;
create table vertex(
id integer
);
create table edge(
src integer,
dest integer,
weight float8
);
insert into vertex values
(0),
(1),
(2),
(3),
(4),
(5),
(6),
(7);
insert into edge values
(0, 1, 1.0),
(0, 2, 1.0),
(0, 4, 10.0),
(1, 2, 2.0),
(1, 3, 10.0),
(2, 3, 1.0),
(2, 5, 1.0),
(2, 6, 3.0),
(3, 0, 1.0),
(4, 0, -2.0),
(5, 6, 1.0),
(6, 7, 1.0);2. 计算从0顶点到各顶点的最短路径
drop table if exists out;
select madlib.graph_sssp(
'vertex', -- 顶点表
null, -- 顶点列名，这里使用缺省值‘id’
'edge', -- 边表
null, -- 边参数，这里全部使用缺省列名
0, -- 计算最短路径的起始顶点
'out'); -- 输出表名
select * from out order by id;查询结果如下：
id | weight | parent
----+--------+--------
0 | 0 | 0
1 | 1 | 0
2 | 1 | 0
3 | 2 | 2
4 | 10 | 0
5 | 2 | 2
6 | 3 | 5
7 | 4 | 6
(8 rows)3. 获得从0到6的最短路径
select madlib.graph_sssp_get_path('out',6) as spath;结果：
spath
-----------
{0,2,5,6}
(1 row)4. 使用非缺省列名
drop table if exists vertex_alt, edge_alt;
create table vertex_alt as select id as v_id from vertex;
create table edge_alt as select src as e_src, dest, weight as e_weight from edge;5. 计算从1顶点到各顶点的最短路径
drop table if exists out_alt;
select madlib.graph_sssp(
'vertex_alt', -- 顶点表
'v_id', -- 顶点列名
'edge_alt', -- 边表
'src=e_src, weight=e_weight', -- 边参数，指定顶点和边长的列名
1, -- 计算最短路径的起始顶点
'out_alt'); -- 输出表名
select * from out_alt order by v_id;结果：
v_id | e_weight | parent
------+----------+--------
0 | 4 | 3
1 | 0 | 1
2 | 2 | 1
3 | 3 | 2
4 | 14 | 0
5 | 3 | 2
6 | 4 | 5
7 | 5 | 6
(8 rows)参考文献：
- Single Source Shortest Path：Madlib官方文档对单源最短路径的说明。
- 在社交网络中，如何去计算中两个人之间的最短路径？：讨论最短路径在社交网络中的一个应用。