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 n nodes numbered 1,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 1 to the node n is a, but Dijkstra's algorithm returns the answer b.

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 1 to the node 2 and has the weight 5. The second edge is from the node 1 to the node 3 and has the weight 1.

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