# Week 13 - Shortest Paths

## Team

Team name:
Date:

Members

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Cas |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Hlib |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | |

## Activities

### Activity 1: Example graph: find the shortest distance
**Which of these 15 paths has the shortest distance?**

*A,B,E,H,L,P,Q*

**Do you need to go over all the possible paths to find the shortest one?**

*Not really, but to be sure you found the shortest, you might have to.*
### Activity 2: Time to relax

bool shortest_paths::relax(const graph::vertex & vertex, const graph::edge & edge) {
    auto point = get_data(vertex);
    auto point_b = get_data(edge.target());
    auto dist = edge.weight() +  point->distance();
    if (point_b->distance() > dist || !point_b->visited()){
        point_b->visit();
        point_b->set_distance(&edge, dist);
        return true;
    }
    return false;
}

### Activity 3: Depth-first traversal

void shortest_paths::compute(const graph::vertex &source) {
    // initialize the shortest paths data
    prepare(source);
    auto traversal = dfs_traversal(source);
    traversal.run();
    relax_all(traversal.post_order(),true);
}

### 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{
        std::reverse(vector.begin(), vector.end());
        for (auto &label : vector) {
            relax(m_graph[label]);
        }
    }
}

Post-order(reversed) solves the shortest path problem
### Activity 5: Cyclic graphs

Everything works as expected, except the EC edge. The programm finds a cycle FEG and breaks from the paths to the edge AB, so the distance from A to C will be:
A->B->C = 2 + 4 = 6.

Everything is good here. The only difference is that in this graph, it finds the EC edge, making the overall distance to C 5.
A->H->->F->G->E->c = 1 + 1 + 1 + 1 + 1 = 5
As a result of that, it changes the subsequent vertex D
C->D = 5 + 1 = 6.

### 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, because the edge from E to F could have a weight of 0 or 1, then the distance A to F could be less than 16, which is less then 16
**Is it possible that the shortest path from vertex "a" to vertex "e" has a distance smaller
than 14 ? Why (not)?**
No, there are only 3 ways to get to the vertex E: from D, F and G. The vertexes are non-negative, then it is impossible to get lower value, going from vertixes F and G
**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)?**
Yes, following the path of A->B->E, only if the edge BE has a distance of -2 or lower.

Another posibillity would be following the path
A->C->F->E, only if the unknown edge FE has a distance of -3 or lower.
### Activity 7: Implementing array-based Dijkstra

### Activity 8: Time complexity of Dijkstra - array-based

### Activity 9: Using a binary heap

### Activity 10: A lazy heap

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

### Activity 12: Dijkstra’s worst-case time complexity - a closer look

## Look back

### What we've learnt

Fill in...

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Fill in...

### How did the group perform?

How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?