5 ms·

(requires constant-time multiplication) from https://en.wikipedia.org/wiki/Shortest_path_problem#Single-source_shortest_paths https://en.wikipedia.org/wiki/Shor

• elikoga 3y ago
  The $n$ in the title refers to the amount of edges.
  • klyrs 3y ago
    You're talking past the parent's point. If the integer weights grow faster than n*, then this algorithm will grow faster than O(n) * integer weights measured in bit-count; log factors from multiplication time ignored