# Week 14 - [Graph] Shortest Paths II

Max Thielen [497441]

Date: 06/13/2021

## Activities

### Activity 1: Applications of negative edges

Perhaps the most important effect is that when negative weights are present low-weight shortest paths tend to have more edges than higher-weight paths.
For positive weights, our emphasis was on looking for shortcuts;
but when negative weights are present, we seek detours that use as many edges with negative weights as we can find.
This effect turns our intuition in seeking "short" paths into a liability in understanding the algorithms,
so we need to suppress that line of intuition and consider the problem on a basic abstract level.

### Activity 2: Dijkstra on graphs with negative edges


* In which order does Dijkstra’s algorithm relax the six vertices of this graph?

a-c-b-e-d-f
* Did Dijkstra’s algorithm solve the shortest paths problem for this graph? Why (not)?

No, the algorithm fails to find the shortest path since with that order of relaxing each vertex would find the shortest distance to f to be 5 instead of 3.

### Activity 3: Shortest paths trees


* Are these paths the shortest paths possible?

No.

* If shorter paths exist, the distances to which vertices can be further decreased?

Vertices d and f could have a shorter path from a.

* If shorter paths exist, which vertices need to be relaxed to update the shortest paths, and in which order?

Vertices b and d would have to be relaxed.

### Activity 4: Do it yourself

* How many passes are necessary to compute the correct shortest distances for each vertex?

When going in reversed topological order, five passes are required.

* How many vertex relaxations are performed in total (note that vertices with a distance of "very far" are relaxed as well)?

Through out the five passes, 30 vertex relaxations would occur.

### Activity 5: An easy graph


Since there is no path to a, the path always has to start at a. Also, since a is connected to every vertex in the graph each distance will be set to the smallest distance possible. Therefore there is no difference in relaxation 'order'.
### Activity 6: Worst-case number of passes
* What is the worst-case number of passes needed by the algorithm?

n − 1

* What can you say about the shortest paths tree if this maximum number of passes is needed?

The shortest paths tree must be a single chain

### Activity 7: Bellman-Ford

bool bellman_ford::relax_all(const std::vector<graph::vertex> &vector){
    bool isChanged = false;

    for(const auto &v: vector){

        if(relax(v)){
            isChanged = true;
        }
    }
    return isChanged;
}

### Activity 8: Negative cycles

If you made a business agreement with other companies to transport their products, the edge would be a profit instead of a cost, so you can interpret this weight as a negative cost.

### Activity 9: Negative cycles and shortest paths

For one of the graphs, the algorithm will never stop, because there’s always a vertex that has its distance updated.

### Activity 10: Bellman-Ford with negative cycle detection

void bellman_ford::compute(const graph::vertex &source){
    prepare(source);

    for (int i=0; i<m_graph.vertices().size()-1; i++){
        relax_all(m_graph.vertices());
    }
    m\_cycle\_found=relax_all(m_graph.vertices());
}



### Activity 11: Worst-case time complexity of Bellman-Ford

Worst case time-complexitiy is O(V*E) where V is vertices and E is edges. Each edge is relaxed V − 1 + 1 = V times.

### Activity 12: Comparing algorithms