MADlib——基于SQL的数据挖掘解决方案（28）——图算法之单源最短路径

    图算法指利用特制的线条算图求得答案的一种简便算法。无向图、有向图和网络能运用很多常用的图算法，其中主要包括各种遍历算法（这些遍历类似于树的遍历），寻找最短路径的算法，寻找网络中最低代价路径的算法。这些算法常被用以回答一些与图相关的问题，诸如图是否是连通的，图中两个顶点间的最短路径是什么等等。在数据挖掘领域中，图算法可应用到多种场合，以解决特定问题，如管道优化、路由选择、快递服务、网站通信等。

    本篇介绍图的基本概念和表示方法，并简要说明一些常用的图算法。MADlib 1.10.0 文档中只列出了一种图算法模型，即单源最短路径，因此我们将详细描述该算法及其相关函数。同样也会用一个简单示例，说明MADlib单源最短路径函数的用法。

    在计算中，常将运算方程或实验结果绘制成由若干有标尺的线条所组成的图，称为“算图”。计算时根据已知条件，从有关线段上一点开始，连结相关线段上的点，连线与表示所求量线段的交点即为答案。图算法是对树的拓展，树是自上而下的数据结构，除根节点外，其它每个节点都有一个父节点，从上向下排列。而图没有了父子节点的概念，图中的节点都是平等关系，结果更加复杂。

           图1 无向图                                图2 有向图                        

    在图的概念中，除了顶点和边的概念外，还经常涉及到权值，表示一个顶点到另一个顶点的“代价”，如果顶点不联通，可以认为权值无限大。如果不涉及权值，那么可以认为联通的顶点权值都为1。

    数据结构中经常用邻接表和邻接矩阵表示图。

    图3即为图2所示有向图的邻接表，表中的一个节点对应图中的一个顶点，节点后面的链表是与这个节点联通的节点。

    邻接表常用于表示稀疏图，即节点的边数 

    图4是图1所示无向图的邻接矩阵表示。邻接矩阵是一个

    可以看出，邻接矩阵表示方法所占空间为 

    图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。遍历操作是图的一种基本操作，图的许多操作都建立在遍历的基础之上。在遍历图时，为保证图中各顶点在遍历过程中被访问且仅一次，需要为每个顶点设计一个访问标记，设置一个数组，用于标识图中哪个顶点被访问过。数组元素的初始值全部为0，表示顶点均未被访问过。某个顶点被访问后，将相应访问标志数组中的值设为1，以表示该顶点已经被访问。通常图的遍历有两种：深度优先遍历搜索和广度优先遍历搜索。

    深度优先遍历是尽可能“深"的遍历图。假设从节点 

                         开始遍历，遍历与 

    图的广度优先遍历有点像树的层次遍历，是一个分层搜索的过程。假设从 

    对于有 n 个顶点的无向连通图，至少有 n-1 条边，而生成树恰好有 n-1 条边，所以生成树是图的极小连通子图。如果无向连通图是一个网，那么它的所有生成树中必有一棵边的权值总和最小的生成树，称这颗生成树为最小生成树。

    最小生成树是通过贪心算法来构建，通过局部最优来达到整体最优。设 

    最小生成树可以用Kruskal算法或Prim算法求出。在Kruskal算法中，A 是一个森林，将权值进行排序，选取权值最小的边，若选取的边不形成回路，则为安全边，把它添加到正在生长的森林中。在Prim算法中，A 中的边形成单树，每次循环向 A 中添加一个顶点（权值最小的边连接的顶点）。在算法实现中用到一个最小优先级队列，不在树中的顶点都放在基于权值 key 的最小优先级队列 Q 中，对于顶点 v 来说， key[v] 的值是与树 A 中某一顶点连接的某一条边的最小权值，如果不连接，那么 

    此问题求从一个源点到其它各点的最短路径。求解单源最短路径的算法主要有Dijkstra算法和Bellman-Ford算法，其中Dijkstra算法用来解决所有边的权为非负的单源最短路径问题，而Bellman-Ford算法可以适用于更一般的问题，图中边的权值可以为负。MADlib的单源最短路径函数就是使用Bellman-Ford算法实现的。如果要得到每一对顶点之间的最短路径，可使用Floyd算法来求解。

    给定一个带权有向图 

    Dijkstra算法是一种典型最短路径算法，用于计算一个节点到其它所有节点的最短路径。不过，它针对的是非负权值边。其主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率较低。

    Dijkstra 算法的输入包含了一个有权重的有向图 G，以及 G 中的一个来源顶点 S 。我们以 V 表示 G 中所有顶点的集合，以 E 表示 G 中所有边的集合。

    已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低成本路径（最短路径）。这个算法也可以在一个图中，找到从一个顶点 s 到任何其它顶点的最短路径。

    Dijkstra算法无法判断含有负权边图的最短路径。如果遇到负权值，在没有负权回路（回路的权值和为负，即便有负权的边）存在时，可以采用Bellman-Ford算法正确求出最短路径。Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 

    Bellman-Ford算法描述：

graph_sssp( vertex_table,  
            vertex_id,  
            edge_table,  
            edge_args,  
            source_vertex,  
            out_table )

    路径检索函数返回从源顶点到指定目标顶点的最短路径。

graph_sssp( sssp_table,  
            dest_vertex )

    单源最短路径问题是图算法的经典问题，在现实中有很多应用，比如在地图中找出两个点之间的最短距离、最小运费等。社交网络中出现的“六度人脉”功能，可以查看到一个用户和一个陌生人之间可以通过哪几个人认识，也就是所谓的六度关系。这个问题也可抽象为一个单源最短路径问题。将用户作为顶点，用户之间的好友关系作为边，“六度关系”就是两个用户之间的最短路径。在这个特殊场景下，所有边的权重都可认为是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);

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)

dm=# select madlib.graph_sssp_get_path('out',6) as spath; 
   spath   
-----------
 {0,2,5,6}
(1 row)

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;

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)  

    图算法是一类特殊的数据挖掘方法，常被用于解决确定图连通性、寻找最短路径等相关问题。实际应用中，图算法广泛用于社交网络分析（如Community Detection）、互联网（如PageRank）、计算生物学（如研究分子活动路径）、电子工程（如集成电路设计）、科学计算（如图划分）、安全领域（如安全事件分析）等很多方面。图算法主要包括图遍历、图匹配、最小生成树、最短路径等几大类，每一类中有多种算法。MADlib仅提供了一种图算法模型，即单源最短路径模型，它是使用Bellman-Ford算法实现的。