What Is It?
Shortest Path is an algorithm that allows users to calculate the distance from one point to another in a network graph.
Why Is This Important?
Calculating the shortest path between two nodes in a network has many applications. Some examples include analyzing the best origins and destinations for shipping route optimization, or determining the most efficient path for routing communications through a computer network. The shortest path calculation is also used in computing the Graph Distance metrics.
Steps for calculating a Shortest Path on a Network Graph:
- Right-click anywhere in the plot (not on a node) and hover over Network Analysis Tools, then select Shortest Path.
- Click on the first node you would like to use, which become your origin.
- Click on the second node you would like to use, which will be your destination.
- The Shortest Path panel will update with the following information:
- Path Length - the number of edges in the path
- Weight - the sum of edge weights along the identified path
Node Similarity - this uses the Jaccard similarity metric as a representation of node similarity for the path endpoints
- Note: The node similarity metric ranges from 0 to 1, where a value of 1 would represent a perfect overlap in the neighbors of the source and target node.
The method we are using to calculate the shortest path is Djikstra's algorithm, a widely used algorithm in network analysis.