Dijkstra's Shortest Path Analyzer

Visualize Dijkstra's algorithm for finding shortest paths in weighted graphs

1. Algorithm Manual
2. Build Network
3. Algorithm Parameters
4. Visualization

Dijkstra's Algorithm Manual

Learn about Dijkstra's algorithm before using the tool. Dijkstra's algorithm finds shortest paths from a single source in weighted graphs with non-negative weights.

Algorithm Steps

  1. Initialization: Set distance to source as 0 and all other distances as ∞. Create a priority queue with all nodes.
  2. Main Loop: While the priority queue is not empty, extract the node with minimum distance.
  3. Relaxation: For each neighbor of the current node, update distances if a shorter path is found.
  4. Completion: When all reachable nodes are processed, the algorithm terminates.

Pseudocode

function Dijkstra(graph, source):
    // Initialize distances and predecessors
    for each vertex v in graph:
        dist[v] = INFINITY
        prev[v] = UNDEFINED
    dist[source] = 0
    
    // Create a priority queue
    Q = new PriorityQueue(all nodes)
    
    while Q is not empty:
        u = Q.extractMin()  // Node with smallest distance
        
        for each neighbor v of u:
            alt = dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                Q.decreaseKey(v, alt)
    
    return dist, prev

Key Features

  • Finds shortest paths in graphs with non-negative weights
  • Uses a greedy approach with priority queue
  • Time complexity: O((V+E) log V) with binary heap
  • Does not work with negative weight cycles

Applications

  • GPS navigation systems
  • Network routing protocols
  • Social network analysis
  • Transportation and logistics

Ready to Start?

Click the button below to begin building your graph and running Dijkstra's algorithm.