Dijkstra algorithm help

[amoone1]

Hi I'm doing a dijkstra algorithm but ive ended up with an infinite loop do you know how to fix this code so it will give the length of the shortest route?

def dijkstra1(successors, other_node):
    """    
    Parameters
    ----------
    successors : a list of dictionaries, encoding the "successors list" (seen in the lectures)
    other_node : index (an int) of the "target" node "t"

    Returns
    -------
    L[other_node] : the shortest path length from 1 to other_node
    
    """
    #store in a convenient variable (n) the number of nodes |V| in the graph
    n = len(successors)

    #initialize the set S of nodes currently reached with a shortest path
    S = []
    S.append(0)

    L = dict()
    L[0] = 0
    P = dict()
    P[0] = '-'

    #the algorithm iterates until all nodes have been reached (i.e., until len(S) = |V|)
    while len(S) < n:
    return L[other_node]

[j.crater]

Please put your code in Python code tags, you can find help here.

[amoone1]

Yeah sorry about that, new to the forum. I will do so for all future posts.

[micseydel]

I added code tags (which you should include in any future post that involves code), but even if the indentation is wrong, your code doesn't have an infinite loop (even if we gave it input). It's just going to return in the first iteration, there's no way to iterate more than once.

You should also include example input to your function, since right now (after a slight indentation fix) your code runs very quickly but doesn't do anything.

[amoone1]

Write a Python script dijkstra.py containing two functions, dijkstra1() and dijkstra2(), capable of computing the length of a shortest path between the first node of the graph (0) and a second node other_node supplied as input. Note that, in this activity, we are only interested in the length of a shortest path, rather than in the set of arcs it contains. The functions should have two inputs: the successors list of the graph, successors, and the destination node other_node. Assume that successors is implemented as a list of dictionaries where, for all i in V, successors[i] is a dictionary whose keys are the indices of the nodes adjacent to node i and whose values are the lengths of the arcs from i to such nodes. The function dijkstra1() should contain an implementation of Dijkstra’s algorithm which solves the Single Source shortest path problem by computing the shortest path length between 0 and each other node in the graph), modified to return, at the very end of the algorithm, the length of a shortest path between s=0 and t=other_node. The function dijkstra2() should contain a modified implementation which, after the destination node other_node has been reached, halts the execution of the algorithm. Its return value should be the same as dijkstra1().

I'm having trouble understanding where to start with this but whether I have to create a function for the successors and what the difference between djikstra1 and dijkstra2 are. Could anyone explain what these are and give an example code for them please.

[micseydel]

Please don't create multiple threads for what are essentially the same problem. I've merged them here.

[amoone1]

ok thanks

[micseydel]

We're not going to write code for you. You must show an effort and should be asking a question. The question should be minimal to get you unblocked to be able to accomplish the task yourself. If you're not sure where to start, there are lots of resources around - https://python-forum.io/Forum-Tutorials