# 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.