---
# 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) {
}
```

Record your answer here

### 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) {
}
```

### Activity 5: Shortest paths in acyclic graphs

Record your answer here

### Activity 6: Paying a visit only once

Record your answer here

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

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

### Activity 8: Dijkstra using linear search

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

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

Record your answer here

### Activity 10: Using a vertex heap

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

### Activity 11: Minimizing the number of scans

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


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

Record your answer here

### Activity 13: Negative edge weights

Record your answer here

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





