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

Graph – Basic concept
Graph – Shortest path algorithm (You're reading now!)
Graph – Spanning Tree

Content

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.

In order to find the

m i n (A, E)

, we can first find

m i n (A, B)

and

m i n (A, D)

Afterwards, we then compare

m i n (A, B) + w e i g h t (B, E)

and

m i n (A, D) + w e i g h t (D, E)

The smallest one will be the shortest path to E. Using the same way, we can find

m i n (A, B)

and

m i n (A, C)

to get

m i n (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.

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

For example,

m i n (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.

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 (l o g | E |)

. Below, we use priority queue to find the shortest path in

O (| V | l o g | 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.

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

培養與鍛鍊程式設計的邏輯腦第二版

Graph – Shortest path algorithm

Relative articles

Content

Discuss problems

Intuitive idea for finding the shortest path

Algorithm for findind the shortest path

Negetive loop

Summary

Reference

Read more

Graph -- Basic concept

Graph -- Spanning Tree

OpenCV series

OpenCV with Python -- 4