Informasjon

Frist Ingen frist
Innleveringsgrense Ingen begrensning

Logg inn

Graphs - Dijkstra

Dijkstra's algorithm is an algorithm to compute shortest paths in graphs with non-negative edge weights. Denote by \(w(u, v)\) the weight of edge \((u, v)\).

As BFS, we will design the algorithm to receive a source node \(s\) as input and compute the shortest path distances to each other node in the graph.

Let \(dist\) be an array such that \(dist[v]\) is equal to the shortest path distance between node \(s\) and node \(v\). The idea of Dijkstra's algorithm is to keep a set of nodes \(S\) for which we know the value of \(dist\) and grow it until \(S = V\).

Since there are no negative edge weights, we know that \(dist[s] = 0\). This means that we can initialize \(S = \{s \}\). For the other nodes, we initially set \(dist[v] = \infty\).

Given the set \(S\), how can we find a new node to add to it and its distance?

We will consider all edges that go from a node in \(S\) to a node outside of \(S\). From all such edges, we will pick an edge \((u, v)\) such that \(dist[u] + w(u, v)\) is minimum. Then, it is not hard to see that, \(dist[v] = dist[u] + w(u, v)\).

To convince yourself that this is indeed the case, imagine that there is a better way of reaching \(v\). Since \(s \in S\) and :math`v notin S`, this alternative path must at some point exit the set \(S\). Suppose that it does to by an edge \((x, y)\) other than \((u, v)\). The following figure illustrates the situation:

graphs-dijkstra/dijkstra1.png

Then, the path (shown in orange) will have the form \((s, \ldots, x, y, \ldots, v)\). Its cost will be

\begin{equation*} dist[x] + w(x, y) + cost(y, v) \end{equation*}

where

  • \(dist[x]\) is the cost of reaching \(x\) from \(s\)
  • \(w(x, y)\) is the cost of edge \((x, y)\)
  • \(cost(y, v)\) is the cost of the path from \(y\) to \(v\)

On the other hand, the blue path has cost:

\begin{equation*} dist[u] + w(u, v) \end{equation*}

And we must have

\begin{equation*} dist[u] + w(u, v) \leq dist[x] + w(x, y) + cost(y, v) \end{equation*}

because we selected \(u\) such that \(dist[u] + w(u, v) \leq dist[x] + w(x, y)\) and we know that, since the edge weights are non-negative, \(cost(x, y) \geq 0\).

After this discussion it should be quite straightforward for you implement Dijkstra's algorithm. The high level ideas is the following:

  1. Initialize \(dist[s] = 0\) and \(dist[v] = \infty\) for each \(v \neq s\)
  2. Set \(S = \{s\}\)
  3. While \(S \neq V\), pick \((u, v) \in E\) such that \(u \in S, v \notin S\) and \(dist[u] + w(u, v)\) is minimum and set \(dist[v] = dist[u] + w(u, v)\).

Now the only question is how fast can we perform the edge selection in step 3. The naive way of doing so is to simply loop over each node \(u \in S\) and each edge out of \(u\) to check the condition and get the minimum. This would cost \(O(|E|)\) making the algorithm run in \(O(|V| |E|)\) since there are \(|V|\) iterations.

A more efficient alternative is to use a priority queue. A priority queue enables to maintain a queue of ordered elements and retrieve the minimal element in the order efficiently. In our context, the elements will be the edges sorted by their value of \(dist[u] + w(u, v)\).

The Java code doing this is given below. Note that we do not need to explicitly keep track of the set \(S\). In the way the code is written this set is always equal to the set of nodes such that \(dist[u] \neq \infty\).

// class used to represent edges
static class Edge {

    public int orig, dest, cost;

    public Edge(int orig, int dest, int cost) {
        this.orig = orig;
        this.dest = dest;
        this.cost = cost;
    }

}

// class used to compare edges in the priority queue
static class EdgeCmp implements Comparator<Edge> {

    private int[] dist;

    public EdgeCmp(int[] dist) {
        this.dist = dist;
    }

    public int compare(Edge e1, Edge e2) {
        double v1 = dist[e1.orig] + e1.cost;
        double v2 = dist[e2.orig] + e2.cost;
        return Double.compare(v1, v2);
    }

}

static int[] disjktra(LinkedList<Edge>[] g, int s) {
    // initialize distances
    int[] dist = new int[g.length];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[s] = 0;
    // initialize PQ
    PriorityQueue<Edge> Q = new PriorityQueue<>(new EdgeCmp(dist));
    for(Edge e : g[s]) Q.add(e);
    while(!Q.isEmpty()) {
        Edge mine = Q.poll();
        // check whether the edge goes out of S
        if(dist[mine.dest] == Integer.MAX_VALUE) {
            dist[mine.dest] = dist[mine.orig] + mine.cost;
            for(Edge e : g[mine.dest]) {
                Q.add(e);
            }
        }
    }
    return dist;
}

The runtime of this algorithm is \(O(|E| \log(|V|))\) since each edge will be at most one time in the queue and the priority queue poll and add operations are performed in logarithmic time with respect to the size of the queue. The maximum size of the queue is \(|E|\) so the maximum runtime of a queue operation is \(O(\log(|E|)) = O(\log(|V|^2)) = O(\log(|V|))\).

For you algorithmic culture, it is possible to implement Dijkstra's algorithm using a Fibonacci Heap instead of a priority queue reducing the runtime to \(O(|E| + |V| log|V|)\) but this has little to no use in competitive programming.


Single source shortest path

Put the pieces together in order to be able to compute shortest paths in an undirected graph with non negative edge weights.

Input

  • One line with fours integers \(n\), \(m\), \(s\) and \(t\) giving the number of nodes, the number of edges, the source of the path and the destination.
  • \(m\) lines each with with three integers \(u, v\) and \(c\) giving that nodes \(u\) and \(v\) are connected with a bidirectional edge of cost \(c\).

The nodes are numbered starting from 0.

Output

A single integer with the cost of the shortest path from node \(s\) to node \(t\) or the word unreachable.

Constraints

  • \(2 \leq n \leq 50000\)
  • \(1 \leq m \leq 150000\)
  • \(0 \leq s, t < n\)
  • \(0 \leq w \leq 1000\)

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2


Maksimal filstørrelse: 1.0 MiB
Tillatte filetternavn: .java, .cpp, .py