最短路径 #

一、最短路径概述 #

1.1 什么是最短路径 #

最短路径是指两个节点之间经过最少关系数量的路径。

text

示例：
Tom --KNOWS--> Jerry --KNOWS--> Mike --KNOWS--> Alice

Tom到Alice的最短路径：
Tom -> Jerry -> Mike -> Alice (长度=3)

1.2 最短路径函数 #

函数	说明
shortestPath()	返回一条最短路径
allShortestPaths()	返回所有最短路径

二、shortestPath函数 #

2.1 基本语法 #

cypher

MATCH p = shortestPath((a)-[:TYPE*]-(b))
RETURN p

2.2 基本示例 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
RETURN p

2.3 返回路径信息 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
RETURN 
    p AS path,
    length(p) AS distance,
    [n IN nodes(p) | n.name] AS names

2.4 带方向的最短路径 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]->(b:Person {name: 'Jerry'}))
RETURN p

2.5 多种关系类型 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS|FRIEND_OF*]-(b:Person {name: 'Jerry'}))
RETURN p

2.6 限制路径长度 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*..5]-(b:Person {name: 'Jerry'}))
RETURN p

2.7 任意关系类型 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[*]-(b:Person {name: 'Jerry'}))
RETURN p

三、allShortestPaths函数 #

3.1 基本语法 #

cypher

MATCH p = allShortestPaths((a)-[:TYPE*]-(b))
RETURN p

3.2 基本示例 #

cypher

MATCH p = allShortestPaths((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
RETURN p

3.3 返回所有最短路径 #

cypher

MATCH p = allShortestPaths((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
RETURN 
    [n IN nodes(p) | n.name] AS path,
    length(p) AS distance

3.4 统计最短路径数量 #

cypher

MATCH p = allShortestPaths((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
RETURN count(p) AS shortest_path_count

3.5 限制路径长度 #

cypher

MATCH p = allShortestPaths((a:Person {name: 'Tom'})-[:KNOWS*..5]-(b:Person {name: 'Jerry'}))
RETURN p

四、路径过滤 #

4.1 按长度过滤 #

cypher

MATCH p = shortestPath((a)-[:KNOWS*]-(b))
WHERE length(p) > 1
RETURN p

4.2 按节点属性过滤 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
WHERE ALL(n IN nodes(p) WHERE n.status = 'active')
RETURN p

4.3 按关系属性过滤 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[r:KNOWS*]-(b:Person {name: 'Jerry'}))
WHERE ALL(rel IN r WHERE rel.since > 2020)
RETURN p

4.4 排除特定节点 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
WHERE NONE(n IN nodes(p) WHERE n.name = 'Mike')
RETURN p

五、实际应用场景 #

5.1 社交网络：最短关系链 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
RETURN 
    [n IN nodes(p) | n.name] AS connection_path,
    length(p) AS degrees_of_separation

5.2 交通网络：最短路线 #

cypher

MATCH p = shortestPath((a:City {name: 'New York'})-[:CONNECTED_TO*]-(b:City {name: 'Los Angeles'}))
RETURN 
    [n IN nodes(p) | n.name] AS route,
    length(p) AS stops

5.3 组织架构：汇报路径 #

cypher

MATCH p = shortestPath((emp:Employee {name: 'Tom'})-[:REPORTS_TO*]->(ceo:Employee {title: 'CEO'}))
RETURN 
    [n IN nodes(p) | n.name] AS reporting_chain,
    length(p) AS levels

5.4 知识图谱：概念关联 #

cypher

MATCH p = shortestPath((a:Concept {name: 'Graph'})-[:RELATED_TO*]-(b:Concept {name: 'Database'}))
RETURN 
    [n IN nodes(p) | n.name] AS concept_path,
    length(p) AS distance

5.5 供应链：供应路径 #

cypher

MATCH p = shortestPath((product:Product {name: 'iPhone'})-[:SUPPLIED_BY*]-(supplier:Supplier))
RETURN 
    [n IN nodes(p) | n.name] AS supply_chain,
    length(p) AS supply_levels

六、批量最短路径 #

6.1 一对多最短路径 #

cypher

MATCH (a:Person {name: 'Tom'}), (b:Person)
WHERE b.name IN ['Jerry', 'Mike', 'Alice']
MATCH p = shortestPath((a)-[:KNOWS*]-(b))
RETURN b.name, length(p) AS distance, [n IN nodes(p) | n.name] AS path
ORDER BY distance

6.2 多对多最短路径 #

cypher

MATCH (a:Person), (b:Person)
WHERE a.name IN ['Tom', 'Jerry'] AND b.name IN ['Mike', 'Alice']
MATCH p = shortestPath((a)-[:KNOWS*]-(b))
RETURN a.name, b.name, length(p) AS distance
ORDER BY a.name, distance

6.3 使用UNWIND批量查询 #

cypher

:param targets => ['Jerry', 'Mike', 'Alice']
MATCH (a:Person {name: 'Tom'})
UNWIND $targets AS target_name
MATCH (b:Person {name: target_name})
MATCH p = shortestPath((a)-[:KNOWS*]-(b))
RETURN b.name AS target, length(p) AS distance, [n IN nodes(p) | n.name] AS path
ORDER BY distance

七、性能优化 #

7.1 使用索引 #

cypher

CREATE INDEX FOR (p:Person) ON (p.name)

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
RETURN p

7.2 限制路径长度 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*..10]-(b:Person {name: 'Jerry'}))
RETURN p

7.3 指定关系类型 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
RETURN p

7.4 使用PROFILE分析 #

cypher

PROFILE MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
RETURN p

7.5 性能建议 #

text

建议：
├── 使用索引加速节点查找
├── 限制最大路径长度
├── 指定关系类型减少搜索空间
├── 使用PROFILE分析性能
└── 避免在大图上频繁查询

八、高级用法 #

8.1 加权最短路径 #

使用GDS库实现加权最短路径：

cypher

CALL gds.shortestPath.dijkstra.stream('myGraph', {
    sourceNode: gds.findNode('Person', 'name', 'Tom'),
    targetNode: gds.findNode('Person', 'name', 'Jerry'),
    relationshipWeightProperty: 'weight'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN 
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS path_names

8.2 多条最短路径 #

cypher

MATCH p = allShortestPaths((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
WITH length(p) AS dist, collect([n IN nodes(p) | n.name]) AS paths
RETURN dist, paths, size(paths) AS path_count

8.3 最短路径与中间节点 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
WITH p, nodes(p) AS path_nodes
UNWIND range(1, size(path_nodes)-2) AS idx
RETURN path_nodes[idx] AS intermediate_node

8.4 最短路径统计 #

cypher

MATCH (a:Person {name: 'Tom'}), (b:Person)
WHERE a <> b
MATCH p = shortestPath((a)-[:KNOWS*]-(b))
RETURN 
    length(p) AS distance,
    count(DISTINCT b) AS reachable_people
ORDER BY distance

九、常见问题 #

9.1 无路径情况 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Unknown'}))
RETURN p

使用OPTIONAL MATCH处理：

cypher

MATCH (a:Person {name: 'Tom'}), (b:Person {name: 'Unknown'})
OPTIONAL MATCH p = shortestPath((a)-[:KNOWS*]-(b))
RETURN a.name, b.name, p

9.2 自身路径 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(a))
RETURN p

9.3 循环路径 #

cypher

MATCH p = shortestPath((a:Person {name: 'Tom'})-[:KNOWS*]-(b:Person {name: 'Jerry'}))
WHERE size(nodes(p)) = size(apoc.coll.toSet(nodes(p)))
RETURN p

十、实际应用示例 #

10.1 社交网络分析 #

cypher

MATCH (me:User {id: 'user_001'}), (target:User {id: 'user_002'})
MATCH p = shortestPath((me)-[:FRIEND_OF*]-(target))
RETURN 
    [n IN nodes(p) | n.name] AS connection_path,
    length(p) AS degrees_of_separation

10.2 推荐系统 #

cypher

MATCH (me:User {id: 'user_001'}), (potential:User)
WHERE me <> potential AND NOT (me)-[:FRIEND_OF]-(potential)
MATCH p = shortestPath((me)-[:FRIEND_OF*..3]-(potential))
WITH potential, length(p) AS distance, count(p) AS connection_count
ORDER BY distance, connection_count DESC
LIMIT 10
RETURN potential.name, distance, connection_count

10.3 影响力分析 #

cypher

MATCH (influencer:User), (user:User)
WHERE influencer.isInfluencer = true
MATCH p = shortestPath((influencer)-[:INFLUENCES*]-(user))
WITH influencer, count(DISTINCT user) AS reach, avg(length(p)) AS avg_distance
ORDER BY reach DESC
LIMIT 10
RETURN influencer.name, reach, avg_distance

10.4 交通路线规划 #

cypher

MATCH (start:Station {name: 'Station A'}), (end:Station {name: 'Station B'})
MATCH p = allShortestPaths((start)-[:CONNECTED_TO*]-(end))
RETURN 
    [n IN nodes(p) | n.name] AS route,
    length(p) AS stops,
    reduce(total = 0, r IN relationships(p) | total + coalesce(r.distance, 1)) AS total_distance
ORDER BY total_distance
LIMIT 3

十一、总结 #

最短路径要点：

函数	用途	示例
shortestPath	一条最短路径	`shortestPath((a)-[*]-(b))`
allShortestPaths	所有最短路径	`allShortestPaths((a)-[*]-(b))`

最佳实践：

使用索引加速节点查找
限制最大路径长度
指定关系类型减少搜索空间
处理无路径的情况
使用PROFILE分析性能

下一步，让我们学习索引与约束！