Understanding Runtime for Naive Implementation of Dijkstra Algorithm

Question

I am pulling my hair understanding the runtime for the naive (no heap) implementation of Dijsktra algorithm, and potentially if there is a better code for this naive implementation.

The runtime mentioned in theory for naive implementation is O(VE), where E is # of edges and V is the # of Vertices. Is this correct or did I misread? Is this following code running in O(VE) time? How? Is there a better way to implement this naively?

internal void DijkstraShortestPathCompute()
  {
    // initialize shortest paths for s being 0 and rest as indefinite
    // loop until all vertices are explored: hashset condition
    //   loop all the vertices: 1 -> N
    //     find unexplored and vertex with smallest edge
    //   if no smallest edge disconnect and break
    //   Add to hashset
    //   relax its neighbors - update the length of each neighbor if they aren't seen and their current distance smaller than prev
    
    // while all vertices are not explored
    while(Computed.Count < MAX_VERTEX)
    {
      // find the smallest edge
      (int w, int lvw) = (-1, MAX_VALUE);
      for(int j = 1; j <= MAX_VERTEX; j++)
      {
        // only if its not computed before and its dijsktra score is the smalles
        if(!Computed.Contains(j) && ShortestPath[j] < lvw)
        {
          lvw = ShortestPath[j];
          w = j;
        }
      }
      // disconnected graph - walk out
      if(w == -1)
        break;

      // add it to the explored space
      Computed.Add(w);

      // forward relax the edges so that next iteration we can find the smallest potential edges
      foreach((int n, int l) in AdjacencyList[w])
      {
        // if it is not visited and its calculated distance is smallest only then update
        if(!Computed.Contains(n) && ShortestPath[w] + l < ShortestPath[n])
          ShortestPath[n] = ShortestPath[w] + l;
      }
    }
  }

I can see that we are running the outer following loop in O(V-1), where V is # of Vertices

while(Computed.Count < MAX_VERTEX)

The following first inner loop in O(V) times

for(int j = 1; j <= MAX_VERTEX; j++)

and this second inner loop in O(E) times, where E is # of edges

foreach((int n, int l) in AdjacencyList[w])

How come O(V-1 (V + E)) is equal to O(VE)?

What is Computed? What is ShortestPath? Why are they not initialised by the function? — trincot
– trincot, Commented Oct 25, 2024 at 7:14
A comment reads "rest as indefinite": how does "indefinite" work in a comparison? — trincot
– trincot, Commented Oct 25, 2024 at 7:24

trincot · Accepted Answer · 2024-10-25 08:11:17Z

The outer loop iterates 𝑉 times, not 𝑉−1. I assume here that Computed started out as an empty hash set (If you would start Computed with s as member, the inner for loop would not find any candidate, and w would remain -1). And as it starts as empty, and the outer loop exits only when all vertices are in Computed, there are 𝑉 iterations of the outer loop.

You write: "second inner loop in O(𝐸) times", but be aware that AdjacencyList[w] only represents the edges connected to vertex w, not all edges. If you take into consideration that w will take the value of each vertex (the outer loop), then the total number of iterations is O(𝐸). That means that 𝐸 should not be multiplied with 𝑉 (the outer loop), but added separately to the overall work.

Given the first inner loop makes 𝑉 iterations, and does so for each of the 𝑉 iterations of the outer loop, that part of the algorithm represents O(𝑉²). The other inner loop adds 𝐸 to it, so we get: O(𝑉² + 𝐸). But as 𝐸 is at most O(𝑉²) in any simple graph, this term is not significant, and it simplifies to O(𝑉²).

This corresponds to what Wikipedia has on the subject:

The simplest version of Dijkstra's algorithm stores the vertex set 𝑄 as a linked list or array, and edges as an adjacency list or matrix. In this case, extract-minimum is simply a linear search through all vertices in 𝑄, so the running time is Θ(|𝐸| + |𝑉|²) = Θ(|𝑉|²)

The bottleneck in this algorithm is the first inner loop, where you use a linear search to find the unvisited but expanded vertex that has the minimum distance to the start node.

As you know, the efficiency is improved with the use of some form of a priority queue -- for example with a heap -- so that a single search can be completed in Θ(log𝑉) instead of Θ(𝑉).

Collectives™ on Stack Overflow

Understanding Runtime for Naive Implementation of Dijkstra Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related