CODEWITHSUNDEEP
pythonalgorithmdata-structuresgraphbest-first-search
Joachim Gotzz
Joachim Gotzz

Reputation: 1

Find local shortest path with greedy best first search algorithm

Recently I took a test in the theory of algorithms. I had a normal best first search algorithm (code below).

from queue import PriorityQueue

# Filling adjacency matrix with empty arrays
vertices = 14
graph = [[] for i in range(vertices)]


# Function for adding edges to graph
def add_edge(x, y, cost):
    graph[x].append((y, cost))
    graph[y].append((x, cost))


# Function For Implementing Best First Search
# Gives output path having the lowest cost
def best_first_search(source, target, vertices):
    visited = [0] * vertices
    pq = PriorityQueue()
    pq.put((0, source))
    print("Path: ")
    while not pq.empty():
        u = pq.get()[1]
        # Displaying the path having the lowest cost
        print(u, end=" ")
        if u == target:
            break

        for v, c in graph[u]:
            if not visited[v]:
                visited[v] = True
                pq.put((c, v))
    print()


if __name__ == '__main__':
    # The nodes shown in above example(by alphabets) are
    # implemented using integers add_edge(x,y,cost);
    add_edge(0, 1, 1)
    add_edge(0, 2, 8)
    add_edge(1, 2, 12)
    add_edge(1, 4, 13)
    add_edge(2, 3, 6)
    add_edge(4, 3, 3)

    source = 0
    target = 2
    best_first_search(source, target, vertices)

He brings out Path: 0 1 0 2 (path sum — 8), it's correct.

My teacher suggested that I remake the code so that it looks for the local minimum path, i.e. Path: 0 1 2 (path sum — 13).

I need greedily take the shortest edge from the current node to an unvisited node and I don't really understand how to do it right.

Upvotes: 0

Views: 6384

Answers (1)

Thomas
Thomas

Reputation: 181745

Since this is homework, I won't spell out the entire code for you.

For best-first search, you don't need a priority queue. You just need to track which nodes you have visited, and which node you are currently at. While your current node is not the target node, find the shortest edge that leads to an unvisited node, and set your current node to the node at the other end of that edge.

Upvotes: 0

Related Questions