2015

Distance matrix based on Floyd-Warshall algorithm¶

The overall idea is to create a matrix that describes what the shortest distance between each vertex is
Create a matrix of size n*n, where n is the number of vertices
Fill out the matrix with the weights between each set of vertices
Read numbers along the x-axis as "from x" and numbers from the y-axis as "to y"
- From x to y
A row of 0's will always run down across, since the distance from a vertex to ifself is always 0
If it is not possible to go from one vertex to another, write the distance as $\infin$
If the exercise only asks for a single row, i.e the 4th, only fill out the numbers for that row
Update each distance between all vertices by using 1 + k number of edges, if the new distance is shorter
Step 2 uses only a single edge, that is k = 0
If the exercise only asks for a single row, only update numbers for that row
Check each field in the matrix and look at the graph to see if there is a faster way than the last path
Repeat this step as many times as required by the exercise, specified through k

Draw a new graph, called the residual network, with the same vertices as the original but without any edges
For each set of vertices connected by an edge in the original flow network, decide from the following formula if they should be connected in the residual network

The algorithm chooses the path with the lowest flow in the residual network using breath first search (BFS)
The first line in the formula expresses that the arrow should go in the same direction as in the original flow network
The second line in the formula expresses that the arrow should go in the opposite direction as in the original flow network
The third line in the formula expresses that non connected vertices should not be considered
The function f denotes the flow, the first number
The function c denotes the capacity, the last number
Eventually, set u and v to the two vertices involved in the path
If the result is 0 in any case, do not draw the edge in the residual network
See the example below

All points are/should be sorted by their angle to P_0
The angle is calculated from a horizontal line going out from P_0 in both directions

Push the first 3 points onto the stack
Repeat for all points:
While the next point, called P_i, lies to the right or straight ahead in regards to the top two points on the stack:
1. Pop the top point on the stack
2. Check again with the new two top points on the stack
3. Right and left of a point is defined by the line going through the point on top of the stack and the point before it on to the stack
When making a left turn push P_i on top of the stack and go to 2.1
If all points have been checked, the convex hull should have been finished.

A solution to the vertex cover problem, is a set of vertices so that each edge is defined by a least one of the vertices
The minimum vertex cover problem tries to calculate the least amount of vertices that covers all edges
An alternative explanation is police men who has to look down a number of streets, where vertices is places they can stand and edges are streets they have to keep an eye on

There must always be an even number of vertices in the result, since the algorithm always picks a pair of vertices in line 4 and 5

Do until all points have their own box
Draw a line through the point that splits all points in the current box
- If the depth is even, split with regards to the x-axis (draw a vertical line)
- If the depth is uneven, split with regards to the y-axis (draw a horizontal line)
- Since depth starts even, start by splitting with a vertical line
- The exercise will specify whether the point being split is in the left or right subtree, for example based on if it is smaller or equal

The image above shows how each of the points has their own box when the point being split on is in the less or equal box

Last update: June 6, 2020