multixlab

Dijkstra's shortest path algorithm

Algorithms  #graphs  #algorithms  #sssp 

Dijkstra’s algorithm uses edge relaxation to find the shortest path in a director or undirected graph.

Edge relaxation

With edge relaxation, the distance estimates of the vertices are updated by considering the edges incident to the vertices.

As a starting point, all vertices have positive or negative infinity distances. The distances for each vertex are updated according to the following formula. For edge (u,v) if d(u) + e(v) < d(v), update distance in table

Algorithm

The algorithm works by maintaining a priority queue of unexplored vertices, where the priority of a vertex is its distance from the source node. The algorithm iteratively selects the vertex with the smallest distance and explores its neighbors, updating their distances if a shorter path is found. This process continues until all vertices have been explored or the target node has been reached.

  • Example 1
import java.util.*

fun getAdjacentEdgeList():List<List<WeightedEdge>> {
    return mutableListOf<List<WeightedEdge>>().apply {
        add(0, listOf(
                WeightedEdge(1, 6),
                WeightedEdge(3, 2),
                WeightedEdge(2, 2),
        )
        )

        add(
                1, listOf(
                WeightedEdge(0, 6),
                WeightedEdge(3, 8),
                WeightedEdge(5, 2),
                WeightedEdge(4, 3),
        )
        )

        add(
                2, listOf(
                WeightedEdge(0, 2),
                WeightedEdge(3, 6),
                WeightedEdge(6, 8),
        )
        )

        add(
                3, listOf(
                WeightedEdge(0, 2),
                WeightedEdge(1, 8),
                WeightedEdge(2, 6),
                WeightedEdge(6, 3),
                WeightedEdge(4, 4),
        )
        )


        add(
                4, listOf(
                WeightedEdge(3, 4),
                WeightedEdge(1, 3),
                WeightedEdge(7, 2),
                WeightedEdge(6, 1),
        )
        )


        add(
                5, listOf(
                WeightedEdge(1, 2),
                WeightedEdge(7, 7),
        )
        )


        add(
                6, listOf(
                WeightedEdge(4, 1),
                WeightedEdge(3, 3),
                WeightedEdge(2, 8),
        )
        )

        add(
                7, listOf(
                WeightedEdge(5, 7),
                WeightedEdge(4, 2),
        )
        )
    }
}

//sampleStart
fun main() {
    val vertexToAdjacentEdges = getAdjacentEdgeList()
    val startVertex = 0
    dijkstraShortestPath(startVertex, vertexToAdjacentEdges).also {
        println("distance from $startVertex to all other vertices")
        println("Distance: $it")
        println("Vertices: ${it.indices.toList()}")
    }
}

data class VertexWithDistance(val vertex: Int, val distance: Double)
data class WeightedEdge(val value: Int, val weight: Int)

fun dijkstraShortestPath(
        startVertex: Int,
        vertexToAdjacentEdges: List<List<WeightedEdge>>
): List<Int> {
    // click + to see full script
    if (startVertex >= vertexToAdjacentEdges.size || vertexToAdjacentEdges.isEmpty()) {
        return listOf()
    }

    /**
     * Prioritize based on smallest distance
     */
    val queue = PriorityQueue<VertexWithDistance>(Comparator { first, second ->
        (first.distance - second.distance).toInt()
    })

    val totalVertices = vertexToAdjacentEdges.size
    val visited = BooleanArray(totalVertices)
    val distanceTable = Array(totalVertices) { Double.POSITIVE_INFINITY }

    /**
     * Set the start vertex distance to 0
     */
    distanceTable[startVertex] = 0.0
    queue.offer(VertexWithDistance(vertex = startVertex, distance = 0.0))

    while (queue.isNotEmpty()) {
        val (vertex, distance) = queue.poll()
        if (visited[vertex].not()) {
            visited[vertex] = true
            vertexToAdjacentEdges[vertex].forEach { adjacentEdge ->
                val newDistance = distance + adjacentEdge.weight
                val targetVertex = adjacentEdge.value
                // relax edge
                if (newDistance < distanceTable[targetVertex]) {
                    distanceTable[targetVertex] = newDistance
                }
                queue.offer(VertexWithDistance(targetVertex, newDistance))
            }
        }
    }
    return distanceTable.map { it.toInt() }
}
//sampleEnd

Time complexity

The time complexity of Dijkstra’s algorithm depends on the implementation, but the worst-case time complexity is generally O((|E|+|V|)log|V|), where |E| is the number of edges and |V| is the number of vertices in the graph.

The time complexity is dominated by the time required to maintain the priority queue, which requires O(log|V|) time for each insertion or deletion. In the worst case, each vertex and each edge must be processed once, so the total time complexity is O((|E|+|V|)log|V|). However, in practice, the actual running time is often much faster, especially if the graph is sparse.

Drawbacks

Dijkstra’s algorithm has several drawbacks that limit its practicality in certain scenarios:

  1. Limited to non-negative weights: Dijkstra’s algorithm only works with non-negative edge weights. If the graph has negative weights, the algorithm may produce incorrect results or even enter an infinite loop. In such cases, a different algorithm such as the Bellman-Ford algorithm or the Floyd-Warshall algorithm may be more suitable.

  2. Inefficient for large graphs: Dijkstra’s algorithm can become very slow and memory-intensive on large graphs, especially if the graph is dense or has many edges. The time complexity of the algorithm is O((|E|+|V|)log|V|), which can be too slow for graphs with millions of nodes.

  3. Greedy approach: Dijkstra’s algorithm is a greedy approach that always chooses the node with the smallest distance as the next node to explore. While this generally leads to an optimal solution, it may not always be the case, especially in graphs with complex edge weights.

  4. Requires a single source and destination: Dijkstra’s algorithm is designed to find the shortest path between a single source node and a single destination node. If multiple sources or destinations are involved, the algorithm needs to be run multiple times.

  5. Not suitable for dynamic graphs: Dijkstra’s algorithm is designed for static graphs that do not change over time. If the graph is dynamic and edges can be added or removed, a different algorithm such as the A* algorithm or the Bidirectional Dijkstra’s algorithm may be more appropriate.

Exercise

  • Modify the algorithm to print the shortest path
  • Detect if a vertex is not reachable

Related posts

top