data_structures/graphs/shortest_path.py
def dijkstra(g, source):
    """
    Returns the list of distances and the list of paths
    
    Todo: Add the paths
    """
    order = g.getOrder()

    distances = [INFINITY for k in range(order)]
    predecessors = [None for k in range(order)]

    visited = []
    q = priorityQueue()

    # To get the same result as FW 
    # for neighbor in g.getNeighbors(source):
    #     if g.getWeight(source, neighbor) < distances[source]:
    #         distances[source] = 2* g.getWeight(source, neighbor)
    #         predecessors[source] = neighbor

    q.put((0, source))

    while not q.empty():
        cur_distance, cur_vertex = q.get()
        visited.append(cur_vertex)

        for neighbor in g.getNeighbors(cur_vertex):
            if neighbor not in visited:
                new_distance = cur_distance + g.getWeight(cur_vertex, neighbor)
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    predecessors[neighbor] = cur_vertex
                    q.put((new_distance, neighbor))

    return distances, predecessors

    Returns the list of distances and the list of paths
    
    Todo: Add the paths
    
Returns the list of distances and the list of paths
Todo: Add the paths
Returns the list of distances and the list of paths Todo : Add the paths
def dijkstra(g, source):
    order = g.getOrder()
    distances = [INFINITY for k in range(order)]
    predecessors = [None for k in range(order)]
    visited = []
    q = priorityQueue()
    q.put((0, source))
    while not q.empty():
        cur_distance, cur_vertex = q.get()
        visited.append(cur_vertex)
        for neighbor in g.getNeighbors(cur_vertex):
            if neighbor not in visited:
                new_distance = cur_distance + g.getWeight(cur_vertex, neighbor)
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    predecessors[neighbor] = cur_vertex
                    q.put((new_distance, neighbor))
    return distances, predecessors
def dijkstra ( g , source ) : order = g . getOrder ( ) distances = [ INFINITY for k in range ( order ) ] predecessors = [ None for k in range ( order ) ] visited = [ ] q = priorityQueue ( ) q . put ( ( 0 , source ) ) while not q . empty ( ) : cur_distance , cur_vertex = q . get ( ) visited . append ( cur_vertex ) for neighbor in g . getNeighbors ( cur_vertex ) : if neighbor not in visited : new_distance = cur_distance + g . getWeight ( cur_vertex , neighbor ) if new_distance < distances [ neighbor ] : distances [ neighbor ] = new_distance predecessors [ neighbor ] = cur_vertex q . put ( ( new_distance , neighbor ) ) return distances , predecessors
Returns the list of distances and the list of paths
Todo: Add the paths
Returns the list of distances and the list of paths Todo : Add the paths
"""
    Returns the list of distances and the list of paths
    
    Todo: Add the paths
    """ # To get the same result as FW 
 # for neighbor in g.getNeighbors(source):
 #     if g.getWeight(source, neighbor) < distances[source]:
 #         distances[source] = 2* g.getWeight(source, neighbor)
 #         predecessors[source] = neighbor

g
source