Adversarial Shortest Path

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

A route planner P is to plan a route from some source X to destination Y through a graph (max size of 1000 nodes) whose bi-directional edges have costs. Each time P traverses an edge, P's adversary A knows where P is and can increase the cost of any edge e by a multiplicative factor of 1+sqrt(k) where k is the minimum length of the shortest path from either node in e to Y. (Length just means number of edges.) This is a new rule for 2017. Adversary A can affect the same edge e more than once over several turns, each time by this factor 1 + sqrt(k). P is informed of all changes so has a chance to change the path.

Note however that if P takes the initial graph and takes the shortest path and that path has a single edge anywhere, then A might be able to make that path very expensive.

Both A and P will be told the layout of the graph (which will be fixed for the entire night of the contest) and the source and destination nodes.

The format of the edges of the graph will be
node1, node2

Here is a typical file, but please don't count on anything about the statistics of this file; for example, I might give you a hand-built set of edges that has some shortest paths with choke points. All edges have an initial cost of 1.

Each team will play P and A in each pairwise contest.

Here was a winning strategy from 2016 but where the sqrt(k) factor was not present

Architecture Team

Show the layout of the nodes and edges. Then show the progress of P and show edges change weight as A specifies them. Calculate the running cost of the route so far. If A asks to increase the cost of an edge and that edge doesn't exist, ignore it. If A asks to increase the cost of an edge more than allowed, ignore it. If P asks to traverse an edge and P is not on a node of that edge, then ignore that move. Here is the implementation from 2017 by Chirag and Ojas.