Hide menu

AAPS Advanced Algorithmic Problem Solving

Lab 2


Lab Assignment 2

The recommended deadline for lab 2 is 2014-03-03 kl 12:00

Read the general instructions before you start.

The suggested API below is pseudo code, you have to translate it to your favorite language in an appropriate way. The graph type can vary between different APIs, depending on what extra information, such as weights, markings, flows, etc., is relevant for the problem.

The "recommended time complexity" is what is required to pass the time requirements in Kattis.

Sometimes Kattis does not check exactly what is required for the task. For example, you might be asked to find the shortest path from x to y, while Kattis only asks for the shortest distance. In such a case, you should solve the problem as stated in the lab assignment. That Kattis accepts your solution is a necessary but not sufficient condition to get the points for the task.

Task 2.1 Single source shortest path: non-negative distances (1p)

Kattis problem: shortestpath1

Implement Dijkstras algorithm to find the shortest path from one node to all other nodes in a graph with non-negative edge weights.

Kattis only asks for the shortest distance while your solution should be able to construct the actual shortest paths.

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

Task 2.2 Single source shortest path: time table graphs (1p)

Kattis problem: shortestpath2

Add support to you Dijkstra implementation to handle time table graphs, i.e., graphs where an edge may only be used during certain time intervals. You may implement this separately from Task 2.1.

Kattis only asks for the shortest distance while your solution should be able to construct the actual shortest paths.

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

Task 2.3 Single source shortest path: negative distances (1p)

Kattis problem: shortestpath3

Implement Bellman-Fords algorithm for finding the shortest path from a node to all other nodes in a graph where edge weights may be negative.

Kattis only asks for the shortest distance while your solution should be able to construct the actual shortest paths.

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

Task 2.4 All pairs shortest path (1p)

Kattis problem: allpairspath

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

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

Task 2.5 Minimum spanning tree (1p)

Kattis problem: minspantree

Implement an algorithm for finding a minimum spanning tree, given that one exists.

Suggested API:
tree mst(graph G)

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

Task 2.6 Maximum flow (1p)

Kattis problem: maxflow

Implement an algorithm that finds the maximum flow in a flow graph.

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

Task 2.7: Minimal cut (1p)

Kattis problem: mincut

Implement an algorithm for finding the minimal cut in a flow graph. A minimal cut is a subset U of the nodes V where the sum of the capacities from U to V\U is minimal.

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

Task 2.8: Minimal cost maximum flow (1p)

Kattis problem: mincostmaxflow

Implement an algorithm for finding the maximum flow with the minimal cost in a graph. This is a generalization of maximum flow where each edge both has a capacity and a cost. The cost of a flow through an edge is the flow multiplied by the cost for that edge.

Kattis only asks for the maximal flow and the minimal cost while your solution should be able to construct the actual flow.

Förslag till API: graph max_flow(graph G, vertex s, vertex t)

Task 2.9 Euler path (1p)

Kattis problem: eulerianpath

Implement en algorithm for finding an Euler path through a graph, if one exists.

Suggested API:
edge_list eulerian_path(graph G)

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


Page responsible: Fredrik Heintz
Last updated: 2015-04-27