Creating the greedy algorithm using recursion-CodePudding

For an assignement I have to write a Greedy Algorithm using a recursive function, but I can't seem to figure out how to do this.

The assignement is to make a route to go from one city to another, each time going to the city with the lowest distance between them, but no visit cities multiple times.

For now I have the following code, which is of course far from done as it doesnt even have any recursion and simply doesn't give the right result. I wouldn't be surprised if this code is not even slightly right. The result I get is [1,2,1,1], meaning the route would be from city 0 to 1, to 2, to 1, to 1. The answer should be [1, 2, 3].

I've been trying this code for way too long now and I just can't seem to figure it out. I get the idea of what I have to do: take the index of the lowest distance, check if that index is already in list v, if it is, take the second lowest distance and check again. But I can't figure out how to put this into code and include recursion.

Is anyone able to give me any tips to help me along or link me an example code?

PS I am not allowed to use any import functions, this assignement is for a relatively simple (though not simple for me) programming course at my university

v = []
def append_list_with_nearest_unvisited(visited, distances):                  
    city = 0
    for n in range(len(distances)):
        if city in v:
            i = min(j for j in distances[n] if j > 0) #take lowest distance
            h = min(k for k in distances[n] if k > i) #take second lowest distance because the true lowest distance is a visited city
            city = distances[n].index(h) #city visited is the index of the lowest distance
            v.append(city)
        
        else:
            i = min(j for j in distances[n] if j > 0) #take lowest distance
            city = distances[n].index(i)
            v.append(city)
    print(v)

append_list_with_nearest_unvisited(v, [[0,2,3,4],[2,0,4,5],[3,4,0,6],[4,5,6,0]])

CodePudding user response：

I think what you are asking is something like this

nodes = [0,1,2,3]

distanceMat = [
    [0,2,3,4],
    [2,0,4,5],
    [3,4,0,6],
    [4,5,6,0]
    ]

route = []
distance = []
startNode_ = 0
destinationNode_ = 3



def findRoute(currentNode, destinationNode):
    if currentNode not in route:
        route.append(currentNode)
    if currentNode == destinationNode:
        return
    else:
        shortestDistance = min(j for j in distanceMat[currentNode] if j > 0)
        nextNode = distanceMat[currentNode].index(shortestDistance)
        while nextNode in route:
            shortestDistance = min(k for k in distanceMat[currentNode] if k > shortestDistance)
            nextNode = distanceMat[currentNode].index(shortestDistance)
        route.append(nextNode)
        distance.append(shortestDistance)
        findRoute(nextNode, destinationNode)
        
findRoute(startNode_, destinationNode_)

print('Route: ', route, '\nDistance: ', distance)

CodePudding user response：

Cool question, you could do smth. like this:

def f(visited, dist):
    if visited == []:
        current_node = 0
    else:
        current_node = visited[-1]
    distances = dist[current_node]

    # find node with shortest path
    c=-1
    while True:
        smallest_item = min(j for j in distances if j > c)
        next_node = distances.index(smallest_item)
        if  next_node != 0 and next_node not in visited:
            break
        else:
            c = smallest_item
            
    visited.append(next_node)

    # check whether we seen all nodes:
    if len(visited) == len(dist)-1:
        return visited
    else:
        return f(visited, dist)


route = f([], [[0,2,3,4], [2,0,4,5],[3,4,0,6], [4,5,6,0]])
print(route)