Database Reference
In-Depth Information
This type of operation is a very nice use case for graph algorithms. There are a
coupleofverywell-knownalgorithmsthatwecanbrielyhighlight:
•
The Dijkstra algorithm
: This is one of the best-known algorithms to
calculate the shortest weighted path between two points in a graph,
using the properties of the edges as weights or costs of that link.
•
The A* (A-star) algorithm
: This is a variation of Dijkstra's original ideas, but
itusesheuristicstopredictmoreeficientlytheshortestpathexplorations.As
A* explores potential graph paths, it holds a sorted priority queue of alternate
path segments along the way, since it calculates the "past path" cost and the
"future path" cost of the different options that are possible during the
route exploration.
Dependingontherequiredresult,thespeciicdataset,andthespeedrequirements,
different algorithms will yield different returns.
Web search
No topic chapter treating graphs and graph theory—even at the highest level—will
be complete without mentioning one of the most powerful and widely-used graph
algorithms on the planet,
PageRank
. PageRank is the original graph algorithm,
invented by Google founder Larry Page in 1996 at Stanford University, to provide
better web search results. For those of us old enough to remember the early days of
web searching (using tools such as Lycos, AltaVista, and so on), it provided a true
revolution in the way the Web was made accessible to end users. The following
diagram represents the PageRank graph:
