Lab 2

Submit the following, as a group (it is sufficient that only one of you make the submission):

• A list of which problems you have solved, with links to the corresponding Kattis submissions.
• A short statement of who did what.

(Getting Accepted on Kattis is a necessary but not sufficient condition for passing a lab task. Before starting, read the General Lab Instructions for more details)

Hint: in C++ in particular but also Java it is useful to use iterators to represent vectors/sets/etc.  For an example of this for the longest increasing subsequence task below, see here. An advantage of this approach is that the function does not require the input to be stored in some specific container type, you can use arrays, vector, list, or whatever other container type has the operations needed in the function.

Note that the API suggestions below are to be interpreted as pseudo code, you should translate them to your favorite language as you see fit.

Problems on Kattis: https://kth.kattis.com/courses/DD2458/popup25/assignments/hm2rc2/problems Links to an external site.

Note! The lab description below might have additional requirements that need to be fulfilled (in particular the shortest path problems).  In some cases it might be possible to pass the Kattis tests with a slower algorithm, or Kattis might not test all required functionality.  If you do not fulfill the requirements given below you might still get points deducted when presenting your labs.

Single Source Shortest Paths

Task 2.1: Non-negative weights (1p)

Implement Dijkstra's algorithm for finding the shortest path from a vertex to all other vertices of a graph with non-negative edge weights.

Kattis will only ask for the length of the shortest path, but your solution must also be able to construct paths.

API suggestion:
distance/parent[] shortest_path(graph G, node start)

Task 2.2: Time-table search (1p)

Add support to your Dijkstra implementation to handle time table graphs, where each edge can only be used at certain specific time steps.

It is OK if you do this separately from the basic Dijkstra implementation.

Kattis will only ask for the length of the shortest path, but your solution must also be able to construct paths.

API suggestion:

distance/parent[] shortest_path(graph G, node start)

Task 2.3: Negative Weights (1p)

Implement the Bellman-Ford algorithm for finding the shortest path from a source vertex to all vertices in a graph where edge weights are allowed to be negative.

Kattis will only ask for the length of the shortest path, but your solution must also be able to construct paths.

API Suggestion:
distance/parent[] shortest_path(graph G, node start)

All Pairs Shortest Paths

Task 2.4 (1p)

Implement the Floyd-Warshall algorithm for finding the shortest distance between all pairs of nodes in a graph with edge weights.

API suggestion:
distance[][] shortest_path_all_pairs(graph G)

Spanning Trees

Task 2.5: Minimal Spanning Tree (1p)

Implement some algorithm for finding a minimal spanning tree in a graph, provided one exists.

API suggestion:
tree mst(graph G)

Required time complexity: O( (|E|+|V|)·log(|V|) ).

Flows and Cuts

Task 2.6: Maximum Flow (1p)

Implement an algorithm to find a maximum s-t flow in a flow network.

API suggestion:
graph max_flow(graph G, vertex s, vertex t)

Note: Those of you who have taken the "ADK" course will probably be able to make use of the maxflow lab from that course -- perhaps just as an inspiration source, or perhaps as a pretty much complete solution that just needs some dusting off.

Task 2.7: Minimum Cut (1p)

You get the same input as in the max-flow problem, but need to find a subset U of the vertices V such that s belongs to U but t belongs to V\U and the sum of capacities of edges from U to V\U is minimized.

API suggestion:
vertex_set min_cut(graph G, vertex s, vertex t)

Task 2.8: Minimum Cost Maximum Flow (1p)

The minimum cost maximum flow is a generalization of maximum flow, where the edges have costs (in addition to capacities).  Like in the original problem, the goal is to find a flow of maximum size, but subject to this constraint, you also want the total cost of the flow to be minimized.

The cost of a flow through a specific edge is the amount of flow through the edge, multiplied by the cost of the edge.  The cost of a flow in the graph is the sum of the costs of the flows through each edge.

Implement an algorithm to find a minimum cost maximum flow in a flow network with edge costs.

Kattis will only ask for the size of the maximum flow and the value of the minimum cost, but your solution must also solve the problem of constructing the actual flow.

API suggestion:
graph max_flow(graph G, vertex s, vertex t)

Eulerian Walks

Task 2.9: Eulerian Walk (1p)

Implement an algoritm to find an Eulerian walk in a graph, if such a walk exists.

API suggestion:
edge_list eulerian_path(graph G)

Required time complexity: O(|E| + |V|).