---
# System prepended metadata

title: Week 13 - Shortest Paths

---

# Week 13 - Shortest Paths

## Team

Team name:Error
Date:19/06/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.                                             |Thanh 516467      |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              |Minh 511907     |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |  Kaloyan 511216     |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |Hoa 487272       |
## 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

No, we just need to choose the shortest distance to follow

### Activity 2: Time to relax

```c++
bool shortest_paths::relax(const string &vertex, const graph::edge &edge) {
// TODO: Activity 2 - relax the given edge, possibly updating the distance to the edge's target
    //                    return true if the distance to target of edge has changed, false otherwise
    (void) vertex;
    (void) edge;
    bool result;
    if(vertex==m_source){//first we check if the vertex is the vertex source
        //if yes then we just need to update distance to all adjacent vertexes of vertex source
        if(edge.weight() <get_distance(edge.target().name())){
            set_distance(edge.target().name(),"",edge.weight());
            result= true;
        }
        else{
            result=false;
        }
    }
    else{
        if((edge.weight()+get_distance(vertex))<get_distance(edge.target().name())){
            set_distance(edge.target().name(),vertex,edge.weight()+get_distance(vertex));
            result= true;
        }
        else
            result= false;
    }
    return result;
}
```

Record your answer here

### Activity 3: Depth-first traversal

Record your answer here
void shortest_paths::compute() {
    // TODO Activity 3
    // - Use the visitor class of week 12 to perform a depth-first traversal, and
    //   check if the graph is cyclic or not
    // - Set the m_cyclic_graph member variable below to the correct value

    m_cyclic_graph = false;
    std::stack<string>plan_visit;//to visit vertex
    std::unordered_set<string>path;//track path for visiting vertex
    std::unordered_set<string>visited;//vertexes had been visited and no loop between them
    std::unordered_set<string>post_order_visited;//for post order traversal check
    std::vector<string>pre_order;
    std::vector<string>post_order;
    plan_visit.push(m_source);
    while(!plan_visit.empty()){
          int num_explore_vertexs=0;
          auto v=plan_visit.top();

          for(auto iter=m_graph[v].edges().rbegin();iter!=m_graph[v].edges().rend();iter++) {
              if (!visited.contains(iter->target().name())) {
                  plan_visit.push(iter->target().name());
                  num_explore_vertexs++;
              }
          }
        std::cout<<v<<" "<<num_explore_vertexs<<"\n";
          if(num_explore_vertexs==0){
              plan_visit.pop();
              if(!visited.contains(v)){
                  visited.insert(v);
                  if(!path.contains(v)){
                      pre_order.push_back(v);
                      path.insert(v);
                  }
              }else{
                  path.erase(v);

              }
              if(!post_order_visited.contains(v)){
                  post_order_visited.insert(v);
                  post_order.push_back(v);
              }

          }
          else{
              if(path.contains(v)){
                  m_cyclic_graph=true;
                  break;
              }
              else{
                  path.insert(v);
                  pre_order.push_back(v);

              }
          }

    }
    std::cout<<"preorder: ";
    for(auto i=pre_order.begin();i!=pre_order.end();i++){
        std::cout<<*i<<" ";
    }
    std::cout<<"\npost order: ";
    for(auto i=post_order.begin();i!=post_order.end();i++){
        std::cout<<*i<<" ";
    }


    // 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
        //Note the reverse of post order traversal is topological order
        const auto& order= post_order;
        scan_all(order, true);
    } else {
        // TODO Activity 8, 10 - run Dijkstra's algorithm (linear search or binary heap)
        //dijkstra_lin_search();
        dijkstra_heap();
    }
}

### Activity 4: Scanning all vertices

```c++
void shortest_paths::scan_all(std::vector<std::string> vector, bool reversed) {
 // TODO: Activity 4 - scan all vertices in vector, either in normal or reversed order
    (void) vector;
    (void) reversed;
    if(reversed){
        for(auto iter=vector.rbegin();iter!=vector.rend();iter++){
            for(auto&edge:m_graph[*iter].edges()){
                if(relax(*iter,edge)){
                    continue;
                }
            }
        }
    }else{
        for(auto iter=vector.begin();iter !=vector.end();iter++){
            for(auto&edge:m_graph[*iter].edges()){
                if(relax(*iter,edge)){
                    continue;
                }
            }
        }
    }
}
```

### Activity 5: Shortest paths in acyclic graphs

Record your answer here

Here is the picture of pre_order (not reverse): 
![Imgur](https://imgur.com/MGlP8pc.png)
Here is the image of pre_order (reversed):
![Imgur](https://imgur.com/F043pV0.png)
Here is the image of post order (not reverese):
![Imgur](https://imgur.com/9eZkz0n.png)
Here is the image of post order (reversed):
![Imgur](https://imgur.com/GqLAKw6.png)
As it is clearly to be seen, the reverse post order give us the best result
### Activity 6: Paying a visit only once

Record your answer here
Act 6.1
![Imgur](https://imgur.com/ujyScil.png)
Act 6.2
![Imgur](https://imgur.com/lvPuVYP.png)

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

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

    if(num_scans(m_source)==0){//if the vertex source has not been scanned, then return it
        next=m_source;
        return true;
    }else{
        bool res=false;
        int min_dist=path_data::VERY_FAR;
        //The algorithm for this is to find the vertex with the current shortest distance to the vertex source
        //and that vertex must have not been scanned (if not, then we may create a loop around vertex which we have scanned)
        for(auto i:m_shortest_distances){
            if(get_distance(i.first)>0&& get_distance(i.first)<min_dist&& (num_scans(i.first)==0)){
                next=i.first;
                min_dist= get_distance(i.first);
            }
        }
        if(num_scans(next)==0){
            res= true;
        }
        return res;

    }

}
```

### Activity 8: Dijkstra using linear search

```c++
void shortest_paths::dijkstra_lin_search() {
// TODO: Activity 8 - Dijkstra using linear search
    //                    Use find_next_dijkstra to find next vertex to scan
    string vertex="";
    //The algorithm is simple we just need to find if there is any vertex still need to be scanned
    //and scan it until all the vertexes has been scanned
    while(find_next_dijkstra(vertex)){
       scan(vertex);
        std::cout<<"\nver: "<<vertex;
    }
}
```

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

Record your answer here
the worst-case time complexity of finding the next vertex to visit is :0(n)
The worst-case time complexity of updating the distance of a vertex is 0(n)
the worst-case time complexity of the implementation of Dijkstra that uses linear search is 0(m+n^2)


### Activity 10: Using a vertex heap

```c++
void shortest_paths::dijkstra_heap() {
  // TODO: Activity 10 - Dijkstra using a binary heap (vertex_heap)
    //                     - extract vertex with min. distance & scan it
    //                     - if distance to vertex changes, insert it into heap
    // TODO: Activity 11 - Minimize the nr. of scans
    //create a heap
    vertex_heap heap;
    heap.insert(m_source, 0);
    scan(m_source);
    while(!heap.empty()){
        string cur_vertex=heap.min();//take the vertex with the shortest distance to vertexes source from heap
        string next;//vertex which will be inserted to the heap
        heap.delete_min();
        if(cur_vertex==""){//No vertex left? then stop the loop
            break;
        }
        int min_dist=path_data::VERY_FAR;

        for(auto &edges:m_graph[cur_vertex].edges()){
            //looking for the next vertex to scan it
            if((get_distance(edges.target().name())<min_dist)&& num_scans(edges.target().name())==0){
                min_dist=get_distance(edges.target().name());
                next=edges.target().name();
                scan(next);
            }
        }
        heap.insert(next,min_dist);

    }
}
```

### Activity 11: Minimizing the number of scans

```c++
void shortest_paths::dijkstra_heap() {
  // TODO: Activity 10 - Dijkstra using a binary heap (vertex_heap)
    //                     - extract vertex with min. distance & scan it
    //                     - if distance to vertex changes, insert it into heap
    // TODO: Activity 11 - Minimize the nr. of scans
    //create a heap
    vertex_heap heap;
    heap.insert(m_source, 0);
    scan(m_source);
    while(!heap.empty()){
        string cur_vertex=heap.min();//take the vertex with the shortest distance to vertexes source from heap
        string next;//vertex which will be inserted to the heap
        heap.delete_min();
        if(cur_vertex==""){//No vertex left? then stop the loop
            break;
        }
        int min_dist=path_data::VERY_FAR;

        for(auto &edges:m_graph[cur_vertex].edges()){
            //looking for the next vertex to scan it
            if((get_distance(edges.target().name())<min_dist)&& num_scans(edges.target().name())==0){
                min_dist=get_distance(edges.target().name());
                next=edges.target().name();
                scan(next);
            }
        }
        heap.insert(next,min_dist);

    }
}
```


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

It may be the version we implement using priority queue as we get imediately access to the vertex which has the shortest distance to source vertex

### Activity 13: Negative edge weights

If there is a negative weight edge in the graph, the algorithm cannot be used anymore
![Imgur](https://imgur.com/bJHgunI.png)
We can see that there is no distance updated to get vertex g

## Looking back

### What we've learnt

Difference between cyclic and acyclic graphs.
Know how shortest distances can be computed for an acyclic graph.
Learn Dijkstra’s algorithm.
The difference between the array-based and heap-based implementation of Dijkstra’s algorithm.
The worst-case time complexity of Dijkstra’s algorithm 


### What were the surprises

Nothing

### What problems we've encountered
Nothing

### What was or still is unclear

Nothing

### How did the group perform?

As good as always




