Skip to content
Search

Dijkstra's algorithm

lastmod 2025-09-18created 2015-10-234 edits

In computer science, Dijkstra's algorithm (Dijkstra algorithm) is an algorithm that solves the shortest path problem between a given start point and destination in a directed graph where no edge has a negative weight. It is named after the Dutch computer scientist Edsger Dijkstra. For example, if in a graph the vertices each represent a city and the edges represent the lengths of the roads connecting the cities, Dijkstra's algorithm can find the shortest path between two cities.

Dijkstra's algorithm takes as input a directed weighted graph G and a start point s. Let V be the set of all vertices of graph G, and represent an edge of the graph as the ordered pair (u, v) of start point u and endpoint v. Let E be the set of all edges of G, and represent the edge weights as the function w: E → [0, ∞]. The weight w(u, v) is then the cost (time, distance, etc.) of moving from vertex u to vertex v. The cost of a path is the sum of the weights of all edges along the path. Given any pair of vertices s and t in V, Dijkstra's algorithm finds the lowest-cost path (the shortest path) from s to t. The algorithm can also be used to compute the shortest paths from a given start point s to all other vertices.

See also

Favorite site

  • Wikipedia (en) Description of Dijkstra's algorithm
  • New shortest path algorithm discovered after 41 years | GeekNews
    • Researchers at Tsinghua University in China, in collaboration with Stanford University, made a major advance in the computational complexity of the classic single-source shortest path (SSSP) problem. The work won the Best Paper award at STOC 2025.
    • The traditionally common method is Dijkstra's algorithm, with time complexity O(m + n log n) (n = number of nodes, m = number of edges).
      • The log n term relates to the priority queue or sorting, and no improvement has gone beyond it in the last 40 years.
    • The new algorithm reduces the time complexity to O(m · log^(2/3) n).
      • Since log^(2/3) n grows more slowly than log n (i.e., it increases less than log n), the difference becomes large when the number of nodes is very large.
author Zer0 sitemap