Dijkstra’s Shortest Path

Dijksta's algorithm produces the shortest-path tree relative to some distinguished vertex for a weighted graph. With an unweighted graph, simply preform BFS with previous node until the target is found. Reverse the path with backtracking to identify this path.

Shortest-Path Tree vs Minimum Spanning Tree

Both are some spanning tree from a graph G.
A minimum spanning tree is more generic the shortest path.
- A minimum spanning tree prioritizes connecting all the nodes in a graph such that final sum of the collected edges is minimal.
- A shortest path tree looks at specific vertex, and maximize the a spanning tree such that it minimal to from some starting point to any other vertex in the tree.
- So the main difference is that a shortest path tree produces a minimal tree relative to a vertex while a minimum spanning tree looks at the bigger picture to produce an overall minimal network.

For best visualization and efficiency:
Start with the distinguished vertex or node.
Follow the procedure, by writing down the relative costs next to the node on paper.
When moving onto the new node, only consider the nodes it connects to and update if need be.
Once you’re finished, every node will have an associated cost.

Start with a distinguished vertex
Cumulatively update the costs of all the nodes connected relatively to the currently active node.
1. Update the connected node with the new minimum cost.
Augment to the next lowest costing vertex. This is now the current active node 1.
Mark active node as visited. Once all nodes are visited, the algorithm terminates. Otherwise,
See 2.

Define a priority queue, that will be used as our main selector for which node to chose. Define its comparitor to sort by cumulative weights of each node passed in.
Given a starting vertex s, place all outgoing nodes of s into a priority queue with cumulative weights (starting from 0). Mark s as visited. Mark the remainder as visiting.
Select q_cur = q.top() -> which will be the minimum edge. Mark it as visited. Call q.pop() to delete it.
For each edge i adjacent to q_cur, that is also not visited:
- if its weight in the priority queue is greater than the weight defined by the cur_node + edge weight adjacent, then update it the cumulative node in priority queue.
- If it is a new weight, then add it to the priority queue with the weight = cumulative weight + current edge weight.
Continue until q is empty

Priority-queue: Cumulative node weights will be continually added into the data structure, as well as removed. We want to be able to maintain and $O(logn)$ removal, and insertion.

Negative edge lengths in a graph can potentially provide a non-optimal solution.

Last updated 4 years ago