Yen's algorithm
An algorithm that finds the k cheapest routes between two nodes, rather than only the cheapest.
Example
Three routes run from Ashford to Croydon. Two of them stop once on the way. The third stops twice.
cypher
MATCH (source:Stop {name: 'Ashford'}), (target:Stop {name: 'Croydon'})
CALL gds.shortestPath.yens.stream('roads', {
sourceNode: source,
targetNode: target,
k: 2
})
YIELD index, totalCost, path
RETURN index, totalCost, pathk sets how many routes come back. At k: 2 the call returns the route through Barnet and the route through Dover. The route through Epsom and Fulham is one road longer, so it is left out.
Lessons that use this term
The lesson and course links below open in a new tab.
4 lessons use this term. Results are ordered by term density.
Path Finding with GDS4 mentions
- Challenge: Source-Target Shortest PathUsing the Graph Data Science librarythe Yen's algorithm to identify the three shortest paths from Nashville (BNA) to Phuket1 mention
- Weighted Shortest PathsUsing the Graph Data Science libraryimplementation of Yen's algorithm is stored under the gds.shortestPath.yens namespace in the Neo4j Graph Data Science3 mentions
Analyze Graph Data with Python2 mentions
- Dijkstra's Shortest PathAura Graph Analyticsjust one — Use All Pairs Shortest Path You need k shortest paths — Use Yen's algorithm Weights are all equal — Native Cypher SHORTEST is1 mention
- Yen's K-Shortest PathsAura Graph AnalyticsExplain how Yen's algorithm finds multiple ranked paths between nodes Configure the k parameter to retrieve alternative routes Interpret path1 mention