Related Categories

# Shortest Path

Frequently in network analysis, we would like to know the distance between two points. While typically the path between two points with the smallest distance is just a straight line between the two positions, this is not the case in network analysis. Specifically, in network analysis, we must find a path between the two points along the existing edges. There are many algorithms to find the shortest path between two nodes through a network. Dijkstra’s algorithm is one such algorithm that is widely trusted in the network analytics community.

#### Dijkstra’s Algorithm

Dijkstra’s algorithm works by fixing a source node and iteratively branching out to neighbor’s and computing the shortest path to the frontier nodes. This algorithm accounts for edge weights. At each step in the algorithm, a frontier node is selected from a queue (which is filled with the neighbors of the currently visited/explored nodes). The shortest path from the currently visited nodes is computed using edge weights. Finally, the frontier node is relabeled as a visited/explored node. The algorithm is complete when all the nodes in the network have been labeled as visited/explored.

Ultimately, this gives us the shortest path between the selected source and target nodes.

#### Shortest Path Usage and Interpretation

The Path Length is the number of edges in the path. The Weight is the sum of edge weights along the identified path. Node Similarity uses the Jaccard similarity metric as a representation of node similarity for the path endpoints. 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. 