He probably couldn’t imagine that we’d be blogging about him 1200 years later, but there’s one thing he would have little problem understanding about what makes today’s world tick: algorithms. That’s because he’s *the guy algorithms were named for*.

In this *Graph Databases for Beginners* blog series, I’ll take you through the basics of graph technology assuming you have little (or no) background in the space. In past weeks, we’ve tackled why graph technology is the future, why connected data matters, the basics (and pitfalls) of data modeling, why a database query language matters, the differences between imperative and declarative query languages and predictive modeling using graph theory.

The most classic or basic level of depth-first is an *uninformed* search, where the algorithm searches a path until it reaches the end of the graph, then backtracks to the start node and tries a different path.

On the contrary, dealing with semantically rich graph databases allows for *informed * searches, which conduct an early termination of a search if nodes with no compatible outgoing relationships are found. As a result, informed searches also have lower execution times.

(For the record, Cypher queries and Java graph traversals generally perform informed searches.)

Breadth-first search algorithms conduct searches by exploring the graph one layer at a time. They begin with nodes one level deep away from the start node, followed by nodes at depth two, then depth three, and so on until the entire graph has been traversed. Like so:

As you see above, a breadth-first search starts at a given node (marked `0`

) and then travels to every node that’s only one hop away (marked `1`

) *before* it travels to each node that’s two hops away (`2`

). Then, only after it’s traveled to all of the `2`

nodes would it explore one more hop to the nodes marked `3`

.

Like his super-nerd predecessors – al-Khwarizmi and Euler – Edsger Wybe Dijkstra was super into algorithms and super into graphs. That’s probably why he invented Dijkstra’s algorithm

*in twenty minutes*. Like I said, super-nerd. The goal of Dijkstra’s algorithm is to conduct a breadth-first search with a higher level of analysis in order to find the shortest path between two nodes in a graph. Here’s how it works:

- Pick the start and end nodes and add the start node to the set of solved nodes with a value of 0. Solved nodes are the set of nodes with the shortest known path from the start node. The start node has a value of 0 because it is 0 path-length away from itself.
- Traverse breadth-first from the start node to its nearest neighbors and record the path length against each neighboring node.
- Pick the shortest path to one of these neighbors and mark that node as solved. In case of a tie, Dijkstra’s algorithm picks at random (Eeny, meeny, miny, moe, presumably).
- Visit the nearest neighbors to the set of solved nodes and record the path lengths from the start node against these new neighbors. Don’t visit any neighboring nodes that have already been solved, as we already know the shortest paths to them.
- Repeat steps three and four until the destination node has been marked solved.

*all*of your data). After each node is solved, the shortest path from the start node is known and all subsequent paths build upon that knowledge. Dijkstra’s algorithm is often used to find real-world shortest paths, like for navigation and logistics. Let’s look at an example. After all their hard work, al-Khwarizmi and Euler are going to indulge themselves a bit with an item on both of their bucket lists: A good, old-fashioned road trip across Australia – from Sydney to Perth. But, being super-nerd mathematicians, they want to take the shortest route possible, and they’re going to use Dijkstra’s algorithm to find it. Sydney is the start node and is immediately solved with a value of 0 as our famous duo are already there. Moving in a breadth-first manner, they look at the next cities one hop away from Sydney: Brisbane, Canberra and Melbourne. Canberra is the shortest path at 4 hours, so they count that as solved. They continue looking at the rest of the graph from their solved nodes (from Sydney and from Canberra), considering other nodes and selecting the shortest path. From there, Brisbane at 9 hours is the next solved node. They move on, choosing between Melbourne, Cairns and Alice Springs. Melbourne is the shortest (total) path at 10 hours from Sydney via Canberra, so it becomes their next solved node. Their next options of neighboring nodes (from already solved ones) are Adelaide, Cairns and Alice Springs. At 18 hours from Sydney via Canberra and Melbourne, Adelaide is the next shortest path. The next options are Perth (their final destination), Alice Springs and Cairns. While in reality we know that they should next head directly to Perth, al-Khwarizmi and Euler are still sort of new to this whole “Australia even exists” concept. So, they decide to strictly follow Dijkstra’s algorithm no matter what (this is what a computer would do, after all). According to Dijkstra’s algorithm, Alice Springs is chosen because it has the current shortest path (19 total hours vs. 50 total hours).

Note that because this is a breadth-first search, Dijkstra’s algorithm *must* first search all still-possible paths, not just the first solution that it happens across. This principle is why Perth isn’t immediately ruled out as the shortest path.

Now that al-Khwarizmi and Euler have used Dijkstra’s algorithm to solve for all possible paths, they can rightly compare the two routes to Perth:

- via Adelaide at a cost of 50 hours, or
- via Darwin at a cost of 82 hours

For more information on how the A* algorithm is used in practice, consult Chapter 7 of *Graph Databases* from O’Reilly Media.

This is where your super-nerd friends (or even a helpful ebook, if you don’t have friends) come in handy. If they’re smart, they’ll match the right graph algorithm with the type of results you’re looking for.

But now when they start talking breadth-first vs. depth-first vs. best-first you can tell them you know your A* from your Dijkstra and this isn’t your first rodeo. Go make al-Khwarizmi proud.**You’ve scratched the surface: Now, dive deeper.**

Click below to get your copy of the O’Reilly

Click below to get your copy of the O’Reilly

*Graph Databases*book and start using graph technology to solve real-world problems. *Catch up with the rest of the Graph Databases for Beginners series: *