---
# System prepended metadata

title: Week 13 - Shortest Paths

---

# 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

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

````c
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

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

````c
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

![](https://i.imgur.com/5bUZkMd.jpg)

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

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

````c
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

```c++
void shortest_paths::dijkstra_lin_search() {
}
```

````c
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

```c++
void shortest_paths::dijkstra_heap() {
}
```


````c
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

```c++
void shortest_paths::dijkstra_heap() {
}
```

````c
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
![](https://i.imgur.com/lGb6bm5.jpg)

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?





