# Week 13 - [Graph] Shortest Paths I

Max Thielen [497441]

Date: 06/05/2021

## Activities

### Activity 1: Example graph: find the shortest distance


The quickest way of coming up with a good rout is to look at an intersection of multiple possible edges and chose the one with the least weight. This would be **a**-d-g-k-l-p-**q** coming to a total weight of 16. However, some more playing around reveals that the path **a**-b-c-f-j-m-**q** also totals up to 16 showing that choosing the least heavy weighted edge is not always purely reliable. There could also be a situation where the least
### Activity 2: Time to relax

bool shortest_paths::relax(const graph::vertex & vertex, const graph::edge & edge) {
    if(get_data(vertex)->distance()==0){
        get_data(edge.target())->set_distance(&edge,edge.weight());
        return true;
    }
    else{
        if(get_data(vertex)->distance()+edge.weight()<get_data(edge.target())->distance()){
            get_data(edge.target())->set_distance(&edge,get_data(vertex)->distance()+edge.weight());
            return true;
        }
        return false;
    }
}

### Activity 3: Depth-first traversal

bool shortest_paths::relax(const graph::vertex & vertex, const graph::edge & edge) {
    if(get_data(vertex)->distance()==0){
        get_data(edge.target())->set_distance(&edge,edge.weight());
        return true;
    }
    else{
        if(get_data(vertex)->distance()+edge.weight()<get_data(edge.target())->distance()){
            get_data(edge.target())->set_distance(&edge,get_data(vertex)->distance()+edge.weight());
            return true;
        }
        return false;
    }
}

### Activity 4: Topological sort

void shortest_paths::relax_all(std::vector<std::string> vector, bool reversed) {
    if(!reversed) {
        for (auto &label : vector) {
            relax(m_graph[label]);
        }
    }
    else{
        while(!vector.back().empty()){
            relax(m_graph[vector.back()]);
            vector.pop_back();
        }
    }
}

Reverse DFS postorder will always be a valid topological ordering. This is because a DFS postorder traversal visits nodes only after all successors have been visited, so the reverse traversal visits nodes only after all predecessors have been visited.
### Activity 5: Cyclic graphs


The cyclic graphs prevent a correct topological order for their vertecies. Therefore the previous method for finding the Shortest path through depth first search fails here.

### Activity 6: Is is possible to find a shorter path?
* **Is it possible that the shortest path from vertex "a" to vertex "f" has a distance smaller than 16 ? Why (not)?**

Yes, there is a chance that the path a-c-d-e-f is shorter than a-c-f, since the distance from e to f is still unknown.
If the distance from e to f is between 0 and 1 then the shortest path to f could change.

* **Is it possible that the shortest path from vertex "a" to vertex "e" has a distance smaller than 14 ? Why (not)?**

No, there is no shorter route to e than 14. There are three routes leading to e one of them being the 14 one. The two others are still unkown, however since it is currently assumed no edge can be negative and the shortest paths to f and g have to be greater than or equal to 16, there is no shorter path to e.

* **Suppose that the unknown edge weights can be negative as well. Is it now possible that the shortest path from vertex "a" to vertex "e" has a distance smaller than 14 ? Why (not)?**

Now, there is a possiblilty of finding a shorter path to e. Since f to e could be negative as well as f to g and g to e, the shortest path to f could be reduced from 16 to below 14 through negative edges heading to e.

### Activity 7: Implementing array-based Dijkstra

const graph::vertex *shortest_paths::find_next_dijkstra() {
    graph::vertex * smallest = nullptr;
    int distance = 210000;
    for(auto &var: m_data){
        if(!var.visited() && distance>var.distance()){
            smal    lest = (graph::vertex *) var.vertex();
            distance = var.distance();
        }
    }
    return smallest;
}

void shortest_paths::array_based_dijkstra(const graph::vertex & source) {
    const graph::vertex *next = &source;
    while(next!= nullptr) {
        relax(*next);
        get_data(*next)->visit();
        next = find_next_dijkstra();
    }
}

### Activity 8: Time complexity of Dijkstra - array-based
* **What is the worst-case time complexity of finding the next vertex to visit?**

O(n)

* **What is the worst-case time complexity of updating the distance of a vertex?**

O(1)

* **What is the worst-case time complexity of the array-based implementation of Dijkstra?**

O(n^2+m)

### Activity 9: Using a binary heap
* **What is the worst-case time complexity of finding an element with a given (distance) value in the heap, if the heap contains n elements?**

O(log(n))
* **What effect does decreasing the distances stored in the heap have on the heap invariant?**

If we store these distances in the heap, then we need to locate them before we can decrease them. Even worse, decreasing the distance may cause the heap invariant to be violated, and repairing it costs extra time. This would in fact mean a worst-case time complexity of O(n log n + mn), which is worse than the array-based implementation!

### Activity 10: A lazy heap

void shortest_paths::heap_based_dijkstra(const graph::vertex & source) {
    std::vector<heap_data> heap = { get_data(source) };
    while(!heap.empty()){
        auto var = heap.back().delete_min(heap);
        if(!var.visited()){
            for (const graph::edge &edge : var.vertex()->edges()){
                if(relax(*var.vertex(),edge)){
                    heap.emplace_back(get_data(edge.target()));
                }
            }
            var.visit();
        }
    }
}

### Activity 11: Heap-based Dijkstra - time complexity

* **Question 1**
* What is the worst-case time complexity of the heap-based implementation of Dijkstra, expressed in the number of vertices, n, the number of edges, m, and the number of elements in the heap, h?

O((m + n) log(h))

* Now, how many elements can the heap contain in the worst case?

In the worst case, relaxing a vertex causes the distances of all other (non-relaxed) vertices to be updated. This means that the number of vertices inserted into the heap is n + (n − 1) + (n − 2). . ., which is 1/2n(n + 1), and for sufficiently large n, this is roughly n^2.

* **Question 2**
* What is the worst-case time complexity of the heap-based implementation, expressed only in n and m?

O(log(n) (n + m))

### Activity 12: Dijkstra’s worst-case time complexity - a closer look
* **If we assume a graph with n^2 edges, i.e., set m = n^2, then which of the two versions that we have implemented is the best choice in terms of worst-case time complexity?**

Since the total time complexity for an array based Dijkstra comes out to O(n^2+m), the time complexity would simplify to **O(2n^2)** if m=n^2. Yet when doing the same to the total time complexity of a lazy heap Dijkstra O(2log(n)(m+n)) simplifies to O(2log(n)(n^2+n)) or **O(2n^2log(n)+2nlog(n))**, therefore the array based algorithm would be faster when edges equal n^2.
## Look back

### What we've learnt
Finding the shortest path through a graph with weighted edges using three different methods.

### What were the surprises
The post-order traversal vector finds the shortest path in an acylic graph.

### What problems we've encountered
n/a

### What was or still is unclear
n/a

### How did the group perform?
Well