Shortest path

• To find the shortest path from s to other vertices, we need to keep two arrays.
• dist[] is a V-indexed array, where each index stores the cost of the shortest path to the corresponding vertex (v) from s.
• If it is not possible to reach v from s, the value of dist[v] will either be -1 or infinity, depending on your implementation.
• pred[] is also a V-indexed array, but it stores the predecessor in the shortest path from s, ie. the vertex you come from to get to v quickly.

Edge relaxation

• The process of finding a shorter path is called edge relaxation - this involves updating dist[v] and pred[v] to match a shorter path than what was previously found.
• We do this because dist[] and pred[] show the shortest path found to date.
• Relaxation updates data for w if we find a shorter path from s to w.
• If dist[v] + weight < dist[w], then we update dist[w] to be dist[v] + weight and pred[w] to be v.

Dijkstra's algorithm

dijkstraSSSP(G, source):
    dist[]  // array of cost of shortest path from s
    pred[]  // array of predecessor in shortest path
            // from s
    vSet    // vertices whose shortest path from s is
            // unknown
    initialise all dist[] to infinity/-1
    dist[source] = 0
    initialise all pred[] to -1
    vSet = all vertices of G
    while vSet is not empty:
        find v in vSet with minimum dist[v]
        for each (v, w, weight) in G->edges:
            relax along (v, w, weight)
        vSet = vSet \ {v}

Time complexity

• Each edge needs to be considered once, which is O(E).
• The outer while loop has O(V) iterations.
  • If you try to find the shortest path for every vertex...
    • We have a cost of O(E) to go through each edge.
    • To find the shortest path from the source to somewhere that costs O(V).
    • If we try to do that for each vertex - V times - then the total cost is O(E + V^2), ergo O(V^2).
    • E gets simplified because E < V^2.

int shortestDistance(Graph g, int src, int dest) {
     // Standard BFS
     int nV = GraphNumVertices(g);
     int pred[nV];
     for (int i = 0; i < nV; i++) {
        pred[i] = -1;
     }

     pred[src] = src;
     bool found = false;
     Queue q = QueueNew();
     QueueEnqueue(q, src);

     while (!found && !QueueIsEmpty(q)) {
        int v = QueueDequeue(q);
        for (int w = 0; w < nV; w++) {
            if (GraphIsAdjacent(g, v, w) && pred[w] == -1) {
                pred[w] = v;
                if (w == dest) {
                    found = true;
                }
               QueueEnqueue(q, w);
            }
        }
     }

 QueueFree(q);
 if (pred[dest] == -1) {
    return -1;
 }

 int distance = 0;
 while (dest != src) {
    distance++;
    dest = pred[dest];
 }
 return distance;
}