# Week 13 - Shortest Paths

## Team

Team name: Gappies van andere wappies
Date: 4/7/2022

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. |Stephan|
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Ingmar|
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Ingmar|
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Stijn|

## 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 :heavy_check_mark:

No, 15 is the shortest, ABEHIPQ

### Activity 2: Time to relax :heavy_check_mark:

bool shortest_paths::relax(const string &vertex, const graph::edge &edge) {
    string target_vertex = edge.target();
    int current_distance = get_distance(vertex);
    int target_distance = get_distance(target_vertex);
    int next_distance = current_distance + edge.weight();

    if(next_distance < target_distance) {
        set_distance(target_vertex, vertex, next_distance);
        return true;
    }

    return false;
}

### Activity 3: Depth-first traversal :heavy_check_mark:

void shortest_paths::compute() {
    // Check if the graph has a cyclic
    visitor vis{m_graph, traversal_t::depth_first};
    vis.find_iterative(m_source);
    m_cyclic_graph = vis.cycle_found();

    // based on whether a cycle was found, run a specific shortest paths algorithm
    if (!m_cyclic_graph) {
        // TODO Activity 5 - scan all vertices in topological order
        const auto& order = std::vector<std::string>{};
        scan_all(order, false);
    } else {
        // TODO Activity 8, 10 - run Dijkstra's algorithm (linear search or binary heap)
    }
}

### Activity 4: Scanning all vertices :heavy_check_mark:

void shortest_paths::scan_all(std::vector<std::string> vector, bool reversed) {
    for(std::size_t i = 0; i < vector.size(); ++i) {
        std::size_t true_index = reversed ? vector.size() - 1 - i : i;
        std::string vertex = vector[true_index];
        scan(vertex);
    }
}

### Activity 5: Shortest paths in acyclic graphs :heavy_check_mark:

The reversed post order is the vector that finds the correct shortest path to all vertices. Because when the visitor is backtracking, it has the most effiecient paths to all vertices. :+1:


void shortest_paths::compute() {
    // Check if the graph has a cyclic
    visitor vis{m_graph, traversal_t::depth_first};
    vis.find_iterative(m_source);
    m_cyclic_graph = vis.cycle_found();

    // based on whether a cycle was found, run a specific shortest paths algorithm
    if (!m_cyclic_graph) {
        scan_all(vis.post_order(), true);
    } else {
        // TODO Activity 8, 10 - run Dijkstra's algorithm (linear search or binary heap)
    }
}

### Activity 6: Paying a visit only once :heavy_check_mark:


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

bool shortest_paths::find_next_dijkstra(std::string &next) {
    std::string smallest_vertex{};
    uint32_t smallest_distance = -1;
    for(const auto& vertex: m_graph.vertices()) {
        uint32_t distance = get_distance(vertex.name());
        if(num_scans(vertex) == 0 && distance < smallest_distance) {
            smallest_vertex = vertex.name();
            smallest_distance = distance;
        }
    }

    if(!smallest_vertex.empty()) {
        next = smallest_vertex;
        return true;
    }

    return false;
}

### Activity 8: Dijkstra using linear search :heavy_check_mark:

void shortest_paths::dijkstra_lin_search() {
    bool has_next = true;
    while(has_next) {
        std::string vertex;
        has_next = find_next_dijkstra(vertex);

        if(has_next) {
            scan(vertex);
        }
    }
}

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

- O(n)
- O(m * n)
- O(n^2)

### Activity 10: Using a vertex heap :heavy_check_mark:

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

    while(!heap.empty()) {
        std::string vertex = heap.min();

        for (auto &edge : m_graph[vertex].edges()) {
            if (relax(vertex, edge)) {
                heap.insert(edge.target(), get_distance(edge.target()));
            }
        }
        heap.delete_min();
    }
}

### Activity 11: Minimizing the number of scans :heavy_check_mark:

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

    while(!heap.empty()) {
        std::string vertex = heap.min();

        if(num_scans(vertex) > 0) {
            heap.delete_min();
            continue;
        }

        for (auto &edge : m_graph[vertex].edges()) {
            if (relax(vertex, edge)) {
                heap.insert(edge.target(), get_distance(edge.target()));
            }
        }
        heap.delete_min();
        mark_as_scanned(vertex);
    }
    mark_as_scanned(m_graph.vertices().at(m_graph.vertices().size() - 1));
}

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

A heap based one would be better because it has (v^2*log(v)) , instead of v^2, say you put 2 in it, 2*2*log2 < 2^2

### Activity 13: Negative edge weights
 :heavy_check_mark:

Incorrect:
- b-d.
- d-e.
- d-f.

## Looking back

### What we've learnt
How to deal with different types of dijkstra's algorithm.

### What were the surprises

That a heap based -(dijkstras) algorithm isn't ALWAYS better when for example using negative values.

### What problems we've encountered

Activity 11 was not fully working for us for some reason. But we could not figure out what happened.

### What was or still is unclear

What topological order is.

### How did the group perform?

Very well as always. :)