# 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. | |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | |
| **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
Make sure to have the activities signed off regularly to ensure progress is tracked.

Download the provided project and open it in CLion. **NOTE**: in this week you will have to reuse the code of last week. Follow the instructions given in the `main.cpp` file.

### Activity 1: Find the shortest distance

adgklpq = 16

### Activity 2: Time to relax

bool shortest_paths::relax(const string &vertex, const graph::edge &edge) {
}

bool shortest_paths::relax(const string &vertex, const graph::edge &edge) {
    auto distance = get_distance(vertex)+edge.weight();
    if(distance < get_distance(edge.target())){
        set_distance(edge.target(), vertex, distance);
        return true;
    }
    return false;
}

### Activity 3: Depth-first traversal

Record your answer here

### Activity 4: Scanning all vertices

void shortest_paths::scan_all(std::vector<std::string> vector, bool reversed) {
}

void shortest_paths::scan_all(std::vector<std::string> vector, bool reversed) {
if (reversed){
        for (size_t i = vector.size(); i > 0 ; i–) {
            scan(vector.back());
            vector.pop_back();
        }
}
else
    {
        for (size_t i = 0; i < vector.size(); ++i) {
            scan(vector[i]);
        }
    }
}

### Activity 5: Shortest paths in acyclic graphs


post order reversed
De weg naar j is bij deze methode het kortst

### Activity 6: Paying a visit only once

Zie AS5

### Activity 7: Finding the next vertex to be scanned

bool shortest_paths::find_next_dijkstra(std::string &next) {
}

bool shortest_paths::find_next_dijkstra(std::string &next) {
    //TODO: Activity 7 - go over all vertices that have not been scanned yet,
    // and return the vertex that has the shortest known distance

    string smallest;
    for(auto& vertice: m_graph.vertices()) {
        if (!m_vertex_scans[vertices]) {
            if (get_distance(vertice) < get_distance(smallest) || smallest.empty()) {
                smallest = vertice;
            }
        }
    }
    if (smallest.empty()) return false;
    else{
        next = smallest;
        return true;
    }
}

### Activity 8: Dijkstra using linear search

void shortest_paths::dijkstra_lin_search() {
}

void shortest_paths::dijkstra_lin_search() {
    string vertex;
    while(find_next_dijkstra(vertex)){
        scan(vertex);
        m_vertex_scans[vertex]++;
    }
}

### Activity 9: Time complexity of Dijkstra - linear search

1. O
2. O(1)
3. O(n^2)
### Activity 10: Using a vertex heap

void shortest_paths::dijkstra_heap() {
}

void shortest_paths::dijkstra_heap() {
    // TODO: Activity 10 - Dijkstra using a binary heap (vertex_heap)
    //                     - extract min_vertex with min. distance & scan it
    //                     - if distance to min_vertex changes, insert it into heap


    // TODO: Activity 11 - Minimize the nr. of scans
    vertex_heap heap;
    heap.insert(m_source, 0);

    string min_vertex;
    while (!heap.empty()) {
        min_vertex = heap.min();
        for (auto &edge: m_graph[min_vertex].edges()) {
            if (relax(min_vertex, edge)) heap.insert(edge.target(), get_distance(edge.target()));
        }
        heap.delete_min();
    }
}

### Activity 11: Minimizing the number of scans

void shortest_paths::dijkstra_heap() {
}

void shortest_paths::dijkstra_heap() {
    vertex_heap heap;
    heap.insert(m_source, 0);
    
    string min_vertex;
    while (!heap.empty()) {
        min_vertex = heap.min();
        heap.delete_min();
        if (!num_scans(min_vertex)) {
            for (auto &edge: m_graph[min_vertex].edges()) {
                if (relax(min_vertex, edge)) heap.insert(edge.target(), get_distance(edge.target()));   
            }
            mark_as_scanned(min_vertex);
        }
    }
}

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

Linear is O( n^2 )
Heap base is O(n).
Heap base is in dit geval dus sneller.

### Activity 13: Negative edge weights

Record your answer here

Het algorimte heeft soms niet gelijk de juiste route genomen daarom zijn sommige antwoorden verkeerd.

## Looking back

### What we've learnt

Formulate at least one lesson learned.

### 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?