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 nodes numbered .
- 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 to the node is , but Dijkstra's algorithm returns the answer .
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 to the node and has the weight . The second edge is from the node to the node and has the weight .
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