---
tags: Data structure and algorithm
---

# Graph -- Shortest path algorithm
In the last articles, we talk about the basic concept about graph. Now we are going to talk about the shortest path.

## Relative articles
1. [Graph -- Basic concept](https://hackmd.io/@Justin123/graph1)
2. [Graph -- Shortest path algorithm](https://hackmd.io/@Justin123/graph2) (You're reading now!)
3. [Graph – Spanning Tree](https://hackmd.io/@Justin123/graph3)

## Content
1. [Discussion problems](https://hackmd.io/rbhoKvsgQWmrqyuhMvjmhQ#Discuss-problems)
2. [Intuitive idea for finding the shortest path](https://hackmd.io/rbhoKvsgQWmrqyuhMvjmhQ#Intuitive-idea-for-finding-the-shortest-path)
3. [Algorithm for findind the shortest path](https://hackmd.io/rbhoKvsgQWmrqyuhMvjmhQ#Algorithm-for-findind-the-shortest-path)
4. [Negetive loop](https://hackmd.io/rbhoKvsgQWmrqyuhMvjmhQ#Negetive-loop)
5. [Summary](https://hackmd.io/rbhoKvsgQWmrqyuhMvjmhQ#Summary)
6. [Reference](https://hackmd.io/rbhoKvsgQWmrqyuhMvjmhQ?both#Reference)

## Discuss problems
* **Fastest path**
Justin wanted to buy the latest video games. There were lots of choices for him to reach the department store. How can we find the shortest path for Justin?

---

* **Road Scheduling**
How **Google map** schedule the path for us.

## Intuitive idea for finding the shortest path
Let's say we start from A and we aim to go to E.

graph test {
    // title
    labelloc="t";
    label = "Path\n\n";
    
    rankdir=LR;
    A -- B [label = "2"]
    B -- C [label = "5"]
    A -- C [label = "3"]
    C -- D [label = "9"]
    B -- D [label = "1"]
    B -- E [label = "10"]
    D -- E [label = "3"]
}

In order to find the $min(A, E)$, we can first find $min(A, B)$ and $min(A, D)$.

graph test {
    // title
    labelloc="t";
    label = "Illustration\n\n";
    
    rankdir=LR;
    A -- "..."
    "..." -- "D"
    "..." -- "B"
}

Afterwards, we then compare $min(A, B) \ + weight(B,E)$ and $min(A, D) \ + weight(D, E)$.

graph test {
    // title
    labelloc="t";
    label = "Illustration\n\n";
    
    rankdir=LR;
    A -- "..."
    "..." -- D
    "..." -- B
    D -- E [label = "3", color = "red"]
    B -- E [label = "10", color = "blue"]
}

The smallest one will be the shortest path to E. Using the same way, we can find $min(A, B)$ and $min(A, C)$ to get $min(A, D)$. Below is the pseudocode for shortest path.

// Init the distance from A to all the other vertexs
distance[|V|] <- INF_MAX 

// Function for finding the shortest path
fun findMinDistance(start, sum)
    distance[start] <- sum
    
    for V in adjancent vertex of start
        if (distance[V] > sum + weight(start, V))
            findMinDistance(V, sum + weight(start, V))
        end if
    end for
end fun

// Call the function
findMinDistance(A, 0);

## Algorithm for findind the shortest path
* **Bellman Ford**
In fact, the algorithm we used here is the same in the intuitive part. However, the difference is that it uses the flag to check whether the path is updated or not and break the loop until there are no updating.

    // Edge for DAG
    typedef struct edge {
        int from, to, cost;
    } Edge;

    // Edges
    Edge edges[number_of_edges];

    // Min distance from specific node to others (include itself)
    int d[number_of_vertex];

    // Function for finding the shortest path from one node to others
    void find_shortest(int target) {

        // Init the distance to INF
        fill(d, d + number_of_vertex, INF_MAX);

        // Set the distance to start_node to 0
        d[target] = 0

        while (true) {
            // Flag for checking whether the distance is update or not
            bool update = false;

            for (int i = 0; i < number_of_edge; ++i) {
                Edge next_edge = edges[i];

                // Check whether the distance need to update or not
                if (d[next_edge.from] != INF_MAX &&
                    d[next_edge.to] > d[next_edge.from] + next_edge.cost) {
                        d[next_edge.to] = d[next_edge.from] + next_edge.cost;
                        update = true;
                    }
            }

            // If no update, then break
            if (!update) {
                break;
            }
        }
    }

---

* **Dijkstra**
In fact, we can make progress in **Bellman Ford** algorithm.

1. Update the nodes that are adjacent to the finished node.
2. No repeated uses of the finished node in point 1.

For example, $min(A, B)$ will be decided when we find the weight from A to B. However, in **Bellman Ford** algorithm, we will explore the path from A to B many times.

    graph test {
        // title
        labelloc="t";
        label = "Path\n\n";

        rankdir=LR;
        A -- B [label = "2"]
        B -- C [label = "5"]
        A -- C [label = "3"]
        C -- D [label = "9"]
        B -- D [label = "1"]
        B -- E [label = "10"]
        D -- E [label = "3"]
    }

In normal event, if we start from A, we can decide the shortest path from A to its adjacent nodes. Afterwards, we can decide other shortest paths as well. However, we have to ensure that ==there are no negative weights in graph.== Otherwise, the weights can be updated again and again.

    // Weight for each edge
    int cost[number_of_vertex][number_of_vertex];

    // Min distance from specific node to others (include itself)
    int d[number_of_vertex];

    // Check which vertex being used
    bool used[number_of_vertex];

    void find_shortest(int target) {

        // Init the structure
        fill(d, d + number_of_vertex, INF);
        fill(used, used + number_of_vertex, false);
        d[target] = 0;

        while (true) {
            // vertex to start
            int start = -1;

            // Find the min distance from the not-used edges
            for (int u = 0; u < number_of_vertex; ++u) {
                if (!used[u] &&
                    ((start == -1) || d[u] < d[start])) {
                        start = u;
                }
            }

            // if no update, then break
            if (start == -1) {
                break;
            }

            // Set used to true
            used[start] = true;

            // Update the distance from start to its adjacent vertexs
            for (int v = 0; v < number_of_vertex; ++v) {
                if (!used[v]) {
                    d[v] = min(d[u], d[start] + cost[start][v]);
                }
            }

        }
    }

Here, we have to spend $O(|V|^{2})$ time to find all the nodes and edges. In fact, we can use heap to find the min edges in $O(log|E|)$. Below, we use priority queue to find the shortest path in $O(|V|log|E|)$.

    // Edge for DAG
    typedef struct edge {
        int to, cost;
    } Edge;
    
    // First is the min distance, second is the node's number
    typedef pair<int, int> P;
    
    // Edges
    std::vector<std::vector<Edge> > edges[number_of_nodes];
    edges.resize(number_of_edges, 0);

    // Min distance from specific node to others (include itself)
    int d[number_of_vertex];
    
    void dijkstra(int target) {
        // Heap structure for edges
        std::priority_queue<P, vector<P>, greater<P> > que;
        
        // Init the structure
        std::fill(d, d + number_of_nodes, INF_MAX);
        d[target] = 0;
        
        // Push the first node into the queue
        que.push(P(0, target));
        
        while (!que.empty()) {
            // Pop out min edges
            P p = que.top(); que.pop();
            int v = p.second;
            
            // If the node already updated, then continue
            if (d[v] < p.first) {
                continue;
            }
            
            // Go through all the edges
            for (int i = 0; i < edges[v].size(); ++i) {
                Edge e = edges[v][i];
                
                if (d[e.to] > d[v] + e.cost) {
                    // Update the edge and push it into the queue
                    d[e.to] = d[v] + e.cost;
                    que.push(P(d[e.to], e.to));
                }
            }
        }
    }

---

* **Traces**
In the above session, we only find the number of distances. Now, we want to find how can we reach the shortest path. To achieve this, we only have to use a vector to record the path and update it in the for loop.

    fill(prev, prev + number_of_vertex, -1);
    ...
    
    // Go through all the edges
    for (int i = 0; i < edges[v].size(); ++i) {
        Edge e = edges[v][i];

        if (d[e.to] > d[v] + e.cost) {
            // Update the edge and push it into the queue
            d[e.to] = d[v] + e.cost;
            que.push(P(d[e.to], e.to));
            prev[e.to] = v;
        }
    }
    ...
    std::vector<int> get_path(int target) {
        std::vector<int> path;
        
        // Go through the path
        for (; target != -1; target = prev[target]) {
            path.push_back(target);
        }
        
        // Reverse the path
        std::reverse(path.end(), path.begin());
        return path;
    }
    ...

## Negetive loop
If the graph has negative loop, we will fail to find the shortest path in finite time.

graph test {
    // title
    labelloc="t";
    label = "Path\n\n";
    
    rankdir=LR;
    A -- B [label = "2"]
    B -- C [label = "5"]
    A -- C [label = "-8"]
}

We couldn't find the shortest path in this graph, because **A**, **B** and **C** form a negative loop $(2 + 5 + -8 = -1)$. Therefore, we need a way to detect the negative loop.

To determine the shortest path, we only have to update the distance **(|V| - 1)th** times. Therefore, we can detect that if **|V|th** times is still updating, then there exist at least a negative loop in the graph.

bool find_negative_loop() {
    fill(d, d + number_of_vertex, 0);
    
    for (int i = 0; i < number_of_vertex; ++i) {
        for (int j = 0; j < number_of_edges; ++j) {
            Edge e = edges[j];
            
            if (d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                
                // If times number_of_vertex - 1 still update, 
                // then there are still negative true
                if (i == number_of_vertex - 1) {
                    return true;
                }
            }
        }
    }
    
    return false;
}

## Summary
In this article, we talk about how can we find the shortest path. This is different from going through all the vertexs in the graph which we talked about last time. Also, we learned how to find the shortest path with two different algorithm and also learned how to detect negative loop in a graph. Next time, we will talk about the spanning tree.

## Reference
1. [培養與鍛鍊程式設計的邏輯腦 第二版](https://www.books.com.tw/products/0010616945?gclid=Cj0KCQjwoub3BRC6ARIsABGhnyamNtOnA0U1z3yzZeFonqM2HT7jnj1WZcRX8ArR1_KwV3YEgkkkPlIaAlCZEALw_wcB)