Shortest Path & Dijkstra's Algorithm

Question 1

What is the goal of Shortest path algorithms ?

Answer 1

Find the most efficient route through a graph based on edge weights.

Question 2

What are the variations of shortest path algorithms ?

Answer 2

Single-Source Shortest Path (SSSP): From one node to all others,
Single-Destination Shortest Path (SDSP): from all nodes to one,
All-Pairs Shortest Path (APSP): BEtween every pair of nodes.

Question 3

What is Dijkstra’s Algorithm ?

Answer 3

SSSP algorithm with non-negative weights,
Greedy approach: always picks the node with the shortest know distance,
D array - Distance estimates from the start node,
T array - Tracks which nodes are tight (final shortest distance known)
P array - Records predecessors to reconstruct the actual path.
Array based: O(V^2)
Binary heap: O((V+E) log V)

Question 4

When is Dijkstra’s Algorithm used ?

Answer 4

GPS/Navigation,
Network Routing,
Game AI pathing,
Robotics motion planning.

Question 5

What is a Minimal Spanning Tree (MST) ?

Answer 5

A subtree of the edges of a graph that connects all nodes within the graph.

Question 6

What is Prim’s Algorithm ?

Answer 6

Starts from a vertex, grows MST by adding the smallest-weight edge from inside the tree,
Best for dense graphs,
Time Complexity: O(|E| + |V| log |V|) with Fibonacci heap.

Question 7

What is Kruskal’s Algorithm ?

Answer 7

Starts with edges; adds the smallest edge that doesnt’t form a cycle using disjoint-set structure,
Best for sparse graphs,
Time Complexity: O(|E| log |V|).