数据库算法

图算法之无权最短路径 - 基于Neo4j实现

本文最后更新于 2021-06-26，距今已有 1,175 天，若文章内容或图片链接失效，请留言反馈。

1. 简介

本文基于Neo4j 3.5版本，采用嵌入式的方法开发，neo4j本身其实已经实现了最短路径算法，本文虽然基于neo4j实现，但是更多的是做算法思想的记录，同时本文讲解的最短路径为无权最短路径。

无权最短路径与带权最短路径不同，带权最短路径可能权重最小的路径并不是路径最短的路径。而无权最短路径，仅按路径长短来衡量，所以求最短路径最合适的方法为广度遍历。
一般网上描述的找最短路径的方法为，从起始点开始广度遍历，找到终止点时停止，这个方法并不是性能最高的方法，本文要说明的是从起始点和终止点双向开始进行广度遍历的算法（双向广搜），可以极大提升找最短路径效率。

2.算法介绍

为什么双向广搜可以提升效率？
因为每增加一度遍历点数量都是指数型的增长的，其中还有大部分点在重复遍历。从起始点和终止点双向进行广度搜索，降低了遍历的点数量。

度：对起始点执行广度遍历的次数，也可以叫做步长。
举个例子：广度搜索的扩展就好像围绕起始点扩展出一个圆，而两个半径为5的圆，面积小于一个半径为10的圆。

如何判断是否已经找到最短路径？
需要维护两个数组，一个数组用于存储被起始点遍历过的点，一个数组存储被终止点遍历过的点。如果终止点遍历到的点已经存在于起始点的数组中，或者相反起始点遍历到的点已经存在于终止点的数组中，那么可以确定已经找到了最短路径。
算法再优化
在上面我们已经实现了双向广搜，但是双向广度遍历都是每次遍历一度，在最后找到最短路径碰撞之后算法停止，而碰撞并不一定是在每一度最后的两个点之间发生。在碰撞之后未遍历的点就是无用遍历。
所以可以在此基础上，创建一个迭代器，每次只迭代遍历上一次遍历结果中的一个点，减少了无用遍历。

3. 执行环境

为了后期还能够重现现在使用的环境，简单做个环境记录：

<dependency>
    <!-- 服务器开发需要的jar包 -->
    <groupId>org.neo4j.driver</groupId>
    <artifactId>neo4j-java-driver</artifactId>
    <version>1.5.0</version>
</dependency>
<dependency>
    <!-- 嵌入式开发需要的jar包 -->
    <groupId>org.neo4j</groupId>
    <artifactId>neo4j</artifactId>
    <version>3.5.13</version>
</dependency>
<dependency>
    <!-- 算法包 -->
    <groupId>org.neo4j</groupId>
    <artifactId>neo4j-graph-algo</artifactId>
    <version>3.5.13</version>
</dependency>

嵌入式开发连接Neo4j数据库的程序实现：

public class EmbeNeo4jSource implements Source<GraphDatabaseService>{
    private GraphDatabaseService graphDb;
    private static EmbeNeo4jSource source;

    private EmbeNeo4jSource(){
	// 实际上连接数据库的代码，就这一行实现
        graphDb = new GraphDatabaseFactory().newEmbeddedDatabase(new File("neo4j/" + Config.GRAPH_NAME));
    }

    public static EmbeNeo4jSource build(){
        if (source == null){
            source = new EmbeNeo4jSource();
        }
        return source;
    }

    @Override
    public GraphDatabaseService getDataBase() {
        return graphDb;
    }

    @Override
    public void close() {
        graphDb.shutdown();
    }
}

Neo4j官方最短路径算法示例：https://neo4j.com/docs/java-reference/current/java-embedded/graph-algorithms/index.html

        Node startNode = tx.createNode();
        Node middleNode1 = tx.createNode();
        Node middleNode2 = tx.createNode();
        Node middleNode3 = tx.createNode();
        Node endNode = tx.createNode();
        createRelationshipsBetween( startNode, middleNode1, endNode );
        createRelationshipsBetween( startNode, middleNode2, middleNode3, endNode );

        // Will find the shortest path between startNode and endNode via
        // "MY_TYPE" relationships (in OUTGOING direction), like f.ex:
        //
        // (startNode)-->(middleNode1)-->(endNode)
        //
        PathFinder<Path> finder = GraphAlgoFactory.shortestPath( new BasicEvaluationContext( tx, graphDb ),
            PathExpanders.forTypeAndDirection( ExampleTypes.MY_TYPE, Direction.OUTGOING ), 15 );
        Iterable<Path> paths = finder.findAllPaths( startNode, endNode );

4. 算法实现

实现最短路径的部分内容，算法核心部分：

public ExecuteResult<Integer> javaapi4(Long startId, Long endId){
    Transaction tx = graphDb.beginTx();
    long startTime = System.nanoTime();
    if (startId <= 0 || startId > maxId || endId <= 0 || endId > maxId){
        long endTime = System.nanoTime();
        return  new ExecuteResult<>(endTime - startTime, 0);
    }
    // 记录起始点、终止点遍历的点，存储遍历度数
    byte[] startids = new byte[(int) (maxId+1)];
    byte[] endids = new byte[(int) (maxId+1)];
    // neo4j的获取点api
    Node startNode = graphDb.getNodeById(startId);
    Node endNode = graphDb.getNodeById(endId);
    // start方向下一步需要遍历的节点
    Collection<Node> sids = new ArrayList<>();
    sids.add(startNode);
    // end方向下一步需要遍历的节点
    Collection<Node> eids = new ArrayList<>();
    eids.add(endNode);
    // 迭代器下一步节点的迭代器，初始为空
    ResourceIterator<Node> sNextRelationships = Iterators.emptyResourceIterator();
    ResourceIterator<Node> eNextRelationships = Iterators.emptyResourceIterator();
    // 度数
    byte sDepth = 0;
    byte eDepth = 0;
    int depth = Integer.MAX_VALUE;
    Node node;
    int id;
    while (true){
        if(!sNextRelationships.hasNext()){
            sNextRelationships.close();
            // 使用自定义迭代MyIterator实现对点迭代器中的点获取边迭代器，从而迭代获取下一度的点
            // 实现了算法原理中的3. 算法再优化
            sNextRelationships = new MyIterator(new ArrayList<>(sids).iterator(),
                   edgeFilter, vertexFilter, javaDire, endNode);
            sids.clear();
            // 迭代取得的内容为空，表示已经不能扩展了，表示没有最短路径
            if (!sNextRelationships.hasNext()){
                break;
            }
            sDepth++;
        }
        node = sNextRelationships.next();
        id = (int) node.getId();
        // 该点还未被遍历过
        if (startids[id] == 0){
            // 将该点添加到下一度需要遍历的点，因为该点还未被遍历过
            sids.add(node);
            startids[id] = sDepth;
            // 该点已经被end方向遍历到过了
            if (endids[id]!=0){
                int d = sDepth + endids[id];
                if (d < depth){
                    depth = d;
                }
                // 因为算法再优化过，end并没有一次扩展一整个度，可能这个点是在end方向当前遍历的度（eDepth）上，也可能是在end上
                // 一次遍历的度(eDepth-1)上。
                // 所以这里还需要再判断，如果这个点小于eDepth，那么这个点一定是最短路径了，可以直接退出，如果等于eDepth还存在可
                // 能在上一次遍历的度上也存在更短的最短路径的情况，所以需要判断一下，不能直接break;
                if (endids[id] < eDepth){
                    break;
                }
            }
        }
        if (!eNextRelationships.hasNext()){
            eNextRelationships.close();
            eNextRelationships = new MyIterator(new ArrayList<>(eids).iterator(), edgeFilter, vertexFilter, java2Dire, startNode);
            eids.clear();
            if (!eNextRelationships.hasNext()){
                break;
            }
            eDepth++;
        }
        node = eNextRelationships.next();
        id = (int) node.getId();
        if (endids[id] == 0){
            eids.add(node);
            endids[id] = eDepth;
            if (startids[id] != 0){
                int d = eDepth + startids[id];
                if (d < depth){
                    depth = d;
                }
                if (startids[id] < sDepth){
                    break;
                }
            }
        }
    }
    long endTime = System.nanoTime();
    tx.success();
    tx.close();
    if (depth == Integer.MAX_VALUE){
        return new ExecuteResult<>(endTime - startTime, 0);
    }
    return new ExecuteResult<>(endTime - startTime, depth);
}

自定义迭代器：
该迭代器模仿Neo4j的NestingResourceIterator迭代器实现，至于为什么不直接用NestingResourceIterator而需要自己写的原因有很多，具体有如下几点：

为了实现根据点、边进行过滤的条件过滤器功能；
neo4j中使用NestingResourceIterator通过点迭代器，再获取边迭代器，然后从边迭代器中取边返回的操作无法接触到，为了实现返回点而不是返回边，所以需要修改。

package com.cl.study.ShortestPath;

import java.util.Iterator;

import org.neo4j.graphdb.Direction;
import org.neo4j.graphdb.Node;
import org.neo4j.graphdb.Relationship;
import org.neo4j.graphdb.ResourceIterator;
import org.neo4j.helpers.collection.Iterators;
import org.neo4j.helpers.collection.PrefetchingResourceIterator;

public class MyIterator extends PrefetchingResourceIterator<Node>
{
    private final Iterator<Node> source;
    private ResourceIterator<Relationship> currentNestedIterator;
    private Node currentSurfaceItem;
    private Filter edgeFilter;
    private Filter vertexFilter;
    private Direction direction;
    private Node node;

    public MyIterator( Iterator<Node> source, Filter edgeFilter, Filter vertexFilter, Direction direction, Node node)
    {
        this.source = source;
        this.edgeFilter = edgeFilter;
        this.vertexFilter = vertexFilter;
        this.direction = direction;
        this.node = node;
    }

    @Override
    protected Node fetchNextOrNull(){
        while (true){
            Relationship relationship = fetchRelNextOrNull();
            if (relationship == null){
                return null;
            }
            if (edgeFilter== null || edgeFilter.gl(relationship.getAllProperties())){
                Node node = relationship.getOtherNode(currentSurfaceItem);
                if (vertexFilter == null || vertexFilter.gl(node.getAllProperties()) || node == this.node){
                    return node;
                }
            }
        }
    }

    protected Relationship fetchRelNextOrNull()
    {
        if ( currentNestedIterator == null ||
            !currentNestedIterator.hasNext() )
        {
            while ( source.hasNext() )
            {
                currentSurfaceItem = source.next();
                close();
                currentNestedIterator = createNestedIterator( currentSurfaceItem );
                if ( currentNestedIterator.hasNext() )
                {
                    break;
                }
            }
        }
        return currentNestedIterator != null && currentNestedIterator.hasNext() ? currentNestedIterator.next() : null;
    }

    protected ResourceIterator<Relationship> createNestedIterator( Node node )
    {
        //返回一度邻居，asResourceIterator实现了缓存功能
        return Iterators.asResourceIterator(node.getRelationships(direction).iterator());
    }

    @Override
    public void close()
    {
        if ( currentNestedIterator != null )
        {
            currentNestedIterator.close();
        }
    }
}

关于过滤器，我这里只是一个简单的判断实现，不是本文重点，一起附上：

package com.cl.study.ShortestPath;

import java.util.List;
import java.util.Map;

public abstract class Filter {
    private Filter nextFilter;

    public boolean gl(Map<String, Object> map){
        Filter f = this;
        while(f !=null){
            if (!f.doGl(map)){
                return false;
            }
            f = f.nextFilter;
        }
        return true;
    }

    protected abstract boolean doGl(Map<String, Object> map);

    public static Filter buildFilter(List<Map<String, String>> prop){
        if (prop == null){
            return null;
        }
        Filter filter = null;
        for (Map<String, String> map : prop){
            Filter f = null;
            switch (map.get("type")){
                case "gte":{
                    f = buildFilter1(map.get("name"), map.get("value"));
                    break;
                }
                case "gt":{
                    f = buildFilter2(map.get("name"), map.get("value"));
                    break;
                }
                case "eq":{
                    f = buildFilter3(map.get("name"), map.get("value"));
                    break;
                }
                case "lt":{
                    f = buildFilter4(map.get("name"), map.get("value"));
                    break;
                }
                case "lte":{
                    f = buildFilter5(map.get("name"), map.get("value"));
                    break;
                }
                case "ne":{
                    f = buildFilter6(map.get("name"), map.get("value"));
                    break;
                }
            }
            if (f !=null){
                f.nextFilter = filter;
                filter = f;
            }
        }
        return filter;
    }

    public static Filter buildFilter1(String name, Object value){
        return new Filter() {
            @Override
            protected boolean doGl(Map<String, Object> map) {
                return map.get(name).toString().compareTo(value.toString()) >=0;
            }
        };
    }

    public static Filter buildFilter2(String name, Object value){
        return new Filter() {
            @Override
            protected boolean doGl(Map<String, Object> map) {
                return map.get(name).toString().compareTo(value.toString()) >0;
            }
        };
    }

    public static Filter buildFilter3(String name, Object value){
        return new Filter() {
            @Override
            protected boolean doGl(Map<String, Object> map) {
                return map.get(name).toString().compareTo(value.toString()) == 0;
            }
        };
    }

    public static Filter buildFilter4(String name, Object value){
        return new Filter() {
            @Override
            protected boolean doGl(Map<String, Object> map) {
                return map.get(name).toString().compareTo(value.toString()) < 0;
            }
        };
    }

    public static Filter buildFilter5(String name, Object value){
        return new Filter() {
            @Override
            protected boolean doGl(Map<String, Object> map) {
                return map.get(name).toString().compareTo(value.toString()) <= 0;
            }
        };
    }

    public static Filter buildFilter6(String name, Object value){
        return new Filter() {
            @Override
            protected boolean doGl(Map<String, Object> map) {
                return map.get(name).toString().compareTo(value.toString()) != 0;
            }
        };
    }
}

如果觉得文章对你有用，请随意赞赏

图数据库

图算法之无权最短路径 - 基于Neo4j实现

https://blog.nineya.com/archives/27.html

作者

殇雪

发布于

2020-09-12

更新于

2021-06-26

许可协议

CC BY 4.0

图算法之无权最短路径 - 基于Neo4j实现

1. 简介

2.算法介绍

3. 执行环境

4. 算法实现

作者

发布于

更新于

许可协议

评论