Djikstra's - kgleong/software-engineering GitHub Wiki

Purpose of Dijkstra's Algorithm

Given a graph, find the shortest path from a starting vertex to any other vertex in the graph.

The algorithm will also determine if a vertex is reachable from teh starting vertex.

Graph Prerequisites

Dijkstra's algorithm has a single limitation: the graph must contain no negative edge weights.

The restriction of not allowing negative edge weights allows graphs with cyles to be considered.

For Directed Acyclic Graphs (DAGs) with negative edge weights, use: Shortest-path-in-a-DAG.

For graphs with negative edge weights, use Bellman-Ford.

Implementation

Dijkstra's algorithm employs a greedy approach that results in finding the optimal solution.

Inputs

  1. A graph.
    • In this case, a list of all vertices in the graph. All vertices contain a list of their outgoing edges.
  2. A starting vertex.
    • All distances and shortest paths will be calculated based on the starting vertex.

Outputs Two data structures will be populated when the algorithm has completed running.

  1. Shortest distance from the starting vertex to each vertex
    • Maps vertices to the shortest distance from the starting vertex, taking all edge weights into account.
  2. Predecessors for all vertices
    • These predecessors lie along the shortest path from the starting vertex to each vertex.
    • A shortest path from the starting vertex to any vertex can be constructed from this data structure.
      • This is because of the property that the shortest path to any vertex is the shortest path to its predecessor plus the edge from its predecessor to itself.

Implementation overview: Similar to Prim's-Minimum-Spanning-Tree algorithm, Dijkstra partitions the graph into two sets:

  1. Vertices for which a shortest path has been determined.
  2. Vertices that have not.

All vertices are added into a priority queue. The queue prioritizes vertices based on the minimum distance from the starting vertex.

The starting vertex is initialized to a distance of 0, since the distance from a vertex to itself is 0.

All other vertex distances are initialized to infinity, or in the sample implementatin below, Integer.MAX_VALUE.

The queue is then polled for the vertex with the minimum distance from the starting vertex until it's empty.

For each vertex returned form the priority queue:

  1. This vertex can be thought of the source vertex.
  2. Examine all outgoing edges to all destination vertices.
  3. For each destination vertex:
    1. Find the distance from the starting vertex to the destination vertex via the source vertex.
      • This is equivalent to taking the shortest distance from the starting vertex to the source vertex and adding it to the edge weight from the source to the destination.
    2. Compare the shortest distance so far for the destination vertex to the sum above.
    3. If going through the source vertex is shorter, then we've found a shorter path!
    4. Update the:
      1. shortest distance to the destination vertex to the distance of the path via the source vertex.
      2. predecessor to the destination vertex to the source vertex.

By the time the queue is empty, all edges will have been considered, and will have been given an opportunity to be added to a shortest path.

public class Dijkstra {
    // All vertices in the graph
    Set<Vertex> vertexList;

    Map<Vertex, Integer> vertexToShortestDistanceMap;
    Map<Vertex, Integer> vertexToPredecessorMap;
    PriorityQueue<Vertex> vertexQueue;

    public Dijkstra (Set<Vertex> vertexList) {
        this.vertexList = vertexList;
    }

    public void calculateShortestPath(Vertex startingVertex) {
        init();

        // Set starting vertex distance to 0.
        vertexToShortestDistanceMap.put(startingVertex, 0);

        while(vertexQueue.peek() != null) {
            // A PriorityQueue returns the minimum value by default.
            Vertex sourceVertex = vertexQueue.poll();

            // Get the shortest distance to the current vertex
            int shortestDistanceToSourceVertex =
                vertexToShortestDistanceMap.get(sourceVertex);

            for(OutgoingEdge edge : vertex.outgoingEdgeList) {
                Vertex destinationVertex = edge.destinationVertex;
                int shortestDistanceToDestinationVertex =
                    vertexToShortestDistanceMap.get(destinationVertex);

                // Relax edge
                int distanceToDestinationViaSource =
                    shortestDistanceToSourceVertex + edge.weight;

                // A shorter distance has been found via this edge!
                if(shortestDistanceToDestinationVertex > distanceToDestinationViaSource) {
                    // Update shortest distance
                    vertexToShortestDistanceMap.put(destinationVertex, distanceToDestinationViaSource);

                    // Update predecessor
                    vertexToPredecessorMap.put(destinationVertex, sourceVertex);

                    // Update vertex priority in queue.
                    // This involves removing and re-adding the vertex so that the queue
                    // can reorder based on the newly updated distance, which the queue's
                    // Comparator uses to compare objects.
                    vertexQueue.remove(destinationVertex);
                    vertexQueue.offer(destinationVertex);
                }
            }
        }
    }

    private void init() {
        vertexToShortestDistanceMap = new HashMap<>();
        vertexToPredecessorMap = new HashMap<>();

        // Initialize priority queue
        Vertex.Comparator comparator = new Vertex.Comparator(vertexToShortestDistanceMap);
        vertexQueue = new PriorityQueue<>(vertexList.size(), comparator);

        // Initialize all distances and add all vertices to the priority queue.
        for(Vertex vertex : vertexList) {
            vertexToShortestDistanceMap.put(vertex, Integer.MAX_VALUE);
            vertexQueue.offer(vertex);
        }
    }
}

public class Vertex {
    public List<OutgoingEdge> outgoingEdgeList;

    public static class Comparator<Vertex> {
        Map<Vertex, Integer> vertexToShortestDistanceMap;

        public Comparator(Map<Vertex, Integer> vertexToShortestDistanceMap) {
            this.vertexToShortestDistanceMap = vertexToShortestDistanceMap;
        }

        @Override
        public int compareTo(Vertex firstVertex, Vertex secondVertex) {
            int firstVertexDistance = vertexToShortestDistanceMap.get(firstVertex);
            int secondVertexDistance = vertexToShortestDistanceMap.get(secondVertex);

            // Order vertices by their distance from the starting vertex.
            return firstVertexDistance - secondVertexDistance;
        }
    }
}

public class OutgoingEdge {
    public Vertex destinationVertex;
    public int weight;
}

Runtime

Using a fibonacci heap for the priority queue will result in a runtime of O(V ln V + E), where:

  • V: number of vertices
  • E: number of edges, bounded by V^2.

References

Add a custom footer
⚠️ **GitHub.com Fallback** ⚠️