CSES - Wrong path

Dijkstra's algorithm might produce an incorrect answer if the graph has edges with negative weights.

Your task is to construct a graph, for which an incorrect answer is returned by the implementation of Dijkstra's algorithm given in the course material. The graph should satisfy the following conditions:

  • The graph has nn nodes numbered 1,2,,n1,2,\dots,n.
  • You can choose the number of edges.
  • Every edge is one-directional and has an integral weight.
  • No two edges have both the same start node and the same target node.
  • The start node and the target node of an edge cannot be the same node.
  • The length of the shortest path from the node 11 to the node nn is aa, but Dijkstra's algorithm returns the answer bb.

In a file pathfail.py, implement the function create_edges that constructs a graph satisfying the above conditions. The function returns the graph as list of edges.

For example, the output list [(1, 2, 5), (1, 3, 1)] means that the graph has two edges. The first edge is from the node 11 to the node 22 and has the weight 55. The second edge is from the node 11 to the node 33 and has the weight 11.

You may construct any graph that satisfies the conditions. You may assume that there exists a graph satisfying the conditions for every set of parameters used in testing your function.

class BellmanFord:
    # you can copy this class from the course material

class Dijkstra:
    # you can copy this class from the course material

def create_edges(n, a, b):
    # TODO

def find_answer(my_class, n, edges):
    nodes = range(1, n + 1)
    finder = my_class(nodes)

    for edge in edges:
        finder.add_edge(edge[0], edge[1], edge[2])

    distances = finder.find_distances(1)
    return distances[n]

if __name__ == "__main__":
    n = 100
    edges = create_edges(n, 42, 1337)

    answer1 = find_answer(BellmanFord, n, edges)
    print(answer1) # 42

    answer2 = find_answer(Dijkstra, n, edges)
    print(answer2) # 1337