GraphAcademy

Graph Data Science

Dijkstra's algorithm

An algorithm that finds the cheapest route between two nodes.

Also written: Dijkstra

Example

Two roads out of Ashford reach Croydon, one directly and one through Barnet.

cypher
MATCH (source:Stop {name: 'Ashford'}), (target:Stop {name: 'Croydon'})
CALL gds.shortestPath.dijkstra.stream('roads', {
  sourceNode: source,
  targetNode: target,
  relationshipWeightProperty: 'cost'
})
YIELD totalCost, path
RETURN path, totalCost

The route through Barnet costs 5. The road straight to Croydon costs 10, so Dijkstra returns the two-road route instead.

Lessons that use this term

The lesson and course links below open in a new tab.

12 lessons use this term. Results are ordered by term density.

Analyze Graph Data with Python37 mentions

  • Dijkstra's Shortest PathAura Graph AnalyticsBefore running Dijkstra's on our logistics network, let's understand what it does, how it works internally, and how to configure it for21 mentions
  • Yen's K-Shortest PathsAura Graph AnalyticsDijkstra's gave you the optimal14 mentions
  • Workshop Complete!Aura Graph AnalyticsCreated ephemeral GDS Sessions for scalable workloads Optimized routes with Dijkstra's shortest path Found alternative paths with Yen's k-shortest paths Learned to run analytics without impacting1 mention
  • Introduction to Aura Graph AnalyticsAura Graph Analyticsthe logistics network remotely from AuraDB Run pathfinding algorithms (Dijkstra, Yen's K-Shortest Paths) Compare historical routes against optimal paths Write results back to the1 mention

Path Finding with GDS9 mentions

Graph Data Science in Practice3 mentions

  • Algorithm CategoriesGDS Foundations| Dijkstra, Yen's K-Shortest | | Node Embeddings | How do I represent this for1 mention
  • Applying AlgorithmsGDS FoundationsDijkstra finds the single shortest path between two2 mentions

Get started with Graph Data Science7 mentions

  • Algorithms overviewWorking with algorithmsfinds the shortest path between two4 mentions
  • Module recap and what's nextWorking with algorithmsPropagation) Pathfinding - Discover optimal routes through networks (Dijkstra) Similarity - Find structurally similar nodes (Node Similarity, FastRP) Embeddings - Create vector1 mention
  • Projection modeling for algorithmsEssential projection techniques(Dijkstra, Yen's) is best1 mention
  • Module recapEssential projection techniquesPropagation) Pathfinding - Discover optimal routes through networks (Dijkstra) Similarity - Find structurally similar nodes (Node Similarity, FastRP) Embeddings - Create vector1 mention

Related terms

pathfinding
A family of algorithms that find routes through a graph. What counts as the best route differs by algorithm.8 shared lessons
FastRP
A node embedding algorithm, short for Fast Random Projection. It builds each node's vector by combining random vectors drawn from the nodes around it.6 shared lessons
node similarity
An algorithm that scores how alike two nodes are by comparing the neighbours they share.6 shared lessons
centrality
How important a node is within a graph. Each centrality algorithm defines importance differently.7 shared lessons
community detection
A family of algorithms that group nodes by how they connect. Each algorithm defines a community differently.7 shared lessons
Louvain algorithm
A community detection algorithm that repeatedly merges nodes into groups for as long as merging raises modularity.7 shared lessons
node embedding
A list of numbers that stands in for a node's position in the graph, so that nodes in similar positions get similar lists.3 shared lessons
Yen's algorithm
An algorithm that finds the k cheapest routes between two nodes, rather than only the cheapest.3 shared lessons

All glossary terms