Single source shortest path - DAG

Algorithms  #algorithms  #graphs  #sssp 

The shortest path on a DAG can be found by using edge relaxation on the topological ordering of the 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

Steps

1. Determine the graph’s topological order
2. To keep track of the distance between each vertex, create a distance table (an array or list)
3. Set all vertices’ initial distances to positive infinity
4. Start with the source vertex and set its distance to zero
5. Pick each vertex in topological order and update distance of adjacent vertices based on above formula
6. If the distance of adjacent vertex can not be improved i.e. greater than the existing distance - skip the update
7. The target vertex will have the shortest distance in the distance table once all vertices have been visited

Illustration

Below is an illustration of edge relaxation and shortest path finding.

Note that all vertices must be picked in topological order.

Example (Kotlin)

• The following code finds the shortest path in the graph above, the shortestPath method can be improved to get the start and end vertices as an input.

import java.util.*

fun main() {
    // Map<Vertex, Distance>
    val adjacencyList = mutableListOf<Map<Int, Int>>().apply {
        add(
            0, mapOf(1 to 8, 2 to 1)
        )
        add(
            1, mapOf(
                2 to 4,
                3 to -2,
                4 to 11
            )
        )
        add(
            2, mapOf(
                3 to 2,
                6 to 11
            )
        )
        add(
            3,
            mapOf(
                4 to -4,
                5 to 5,
                6 to 3
            )
        )
        add(
            4, mapOf(7 to 5)
        )
        add(
            5, mapOf(7 to 10)
        )
        add(
            6, mapOf(7 to 2)
        )
        add(
            7, mapOf()
        )
    }

    shortestPath(adjacencyList).also {
        println("distance ${it.first} -> path ${it.second}")
    }
}

//sampleStart
fun shortestPath(adjacencyList: List<Map<Int, Int>>): Pair<Int, List<Int>> {
    // click + to see full script
    if (adjacencyList.isEmpty()) return Pair(0, listOf())

    /**
     * stores the vertices which improve the distance, this will be
     * used to reconstruct the path
     */
    val relaxedBy = mutableMapOf<Int, Int>()

    val topSortedVertices = topSort(adjacencyList)
    val distanceTable = Array(adjacencyList.size) {
        Double.POSITIVE_INFINITY
    }

    // set start distance to 0
    distanceTable[topSortedVertices[0]] = 0.0

    topSortedVertices.forEach { vertex ->
        val outEdges = adjacencyList[vertex]
        val currentVertexDistance = distanceTable[vertex]
        outEdges.forEach { (adjacentVertex, distance) ->
            // relax edge
            val newDistance = distance.plus(currentVertexDistance)
            // for edge (u,v) if d(u) + e(v) < d(v), update distance in table
            if (newDistance < distanceTable[adjacentVertex]) {
                distanceTable[adjacentVertex] = newDistance
                relaxedBy[adjacentVertex] = vertex
            }
        }
    }

    /**
     * reconstruct the path, for each vertex pick the one
     * which improved its distance
     */
    val path = LinkedList<Int>()
    var next: Int? = adjacencyList.size.dec()
    while (next != null) {
        path.push(next)
        next = relaxedBy[next]
    }
    return Pair(distanceTable.last().toInt(), path.toList())
}
//sampleEnd

fun topSort(adjacencyList: List<Map<Int, Int>>): List<Int> {
    // click + to see full script
    val visited = BooleanArray(adjacencyList.size)
    val sortedVertices = IntArray(adjacencyList.size)

    /**
     * insert position of a vertex in sortedVertices, starting with the last position
     */
    var nextInsertionIndexFromEnd = sortedVertices.size - 1

    // performs dfs traversal on vertex
    fun dfs(vertex: Int) {
        visited[vertex] = true
        adjacencyList[vertex].forEach { (adjacentVertex, _) ->
            if (visited[adjacentVertex].not()) {
                dfs(adjacentVertex)
            }
        }

        /**
         * if there are no other vertices to traverse from current vertex,
         * add this vertex to the next empty space in sortedVertices
         */
        sortedVertices[nextInsertionIndexFromEnd--] = vertex
    }

    // perform dfs on each vertex if not visited
    for (vertex in adjacencyList.indices) {
        if (visited[vertex].not()) {
            dfs(vertex)
        }
    }
    return sortedVertices.asList()
}

Longest Path

In addition to finding the shortest path, the algorithm can also be used to find the longest path. Multiply the edge values with -1 and find the shortest path. Then multiply the shortest path edges with -1 again to get the answer.