import Graph


def dijkstra(adjacency_list, source, target):
    """ To be implemented by students. Should return (distance, path).
        Path should be a list of the vertices in the shortest path
        including the source and target. """
    return 6.433, ['A', 'C', 'D']


def test_dijkstra():
    vertices = [
        ('A', 0, 0),
        ('B', 2, 2),
        ('C', 2, -2),
        ('D', 4, 1),
        ('E', 4, -2),
        ('F', 6, 1)
    ]

    edges = [
        ('A', 'B'),
        ('A', 'C'),
        ('C', 'D'),
        ('B', 'C'),
        ('D', 'F'),
        ('B', 'E'),
        ('A', 'F')
    ]

    graph = Graph.Dijkstra(vertices, edges, 'A', 'D')
    dist1, path1 = graph.get_shortest_path()
    dist2, path2 = dijkstra(graph.adjacency_list, graph.source, graph.target)
    assert abs(dist1-dist2) < 1e-3
    print('Correct distance')
    assert path1 == path2
    print('Correct path')