# 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):
Here is the image of pre_order (reversed):
Here is the image of post order (not reverese):
Here is the image of post order (reversed):
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
Act 6.2
### 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
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
Sign in with Wallet
Connect another wallet