Dijkstra's algorithm Python

Question

Given a graph and a source vertex in the graph, find the shortest paths from source to all vertices in the given graph. Read more here -> Link

Please go through my code and help me out by pointing what's wrong with my logic.

My code:

from collections import defaultdict

global INT_MAX
INT_MAX = 3 ** 38


class Graph:
    def __init__(self, numofVertices):
        self.vertList = defaultdict(list)
        self.numofVertices = numofVertices

    def addEdge(self, u, v, cost):
        self.vertList[u].append((v, cost))
        self.vertList[v].append((u, cost))

    def minDist(self, dist, visited):
        
        for v in range(self.numofVertices):
            if dist[v] < INT_MAX and v not in visited:
                minIndex = v
        return minIndex

    def dijsktra(self, src):
        dist = [INT_MAX] * self.numofVertices
        dist[src] = 0
        visited = set()

        for _ in range(self.numofVertices):
            minVertex = self.minDist(dist, visited)

            visited.add(minVertex)

            for nbr, edgeCost in self.vertList[minVertex]:
                if dist[nbr] > dist[minVertex] + edgeCost and nbr not in visited:
                    dist[nbr] = dist[minVertex] + edgeCost
        return dist


g = Graph(9)
g.addEdge(0, 1, 4)
g.addEdge(0, 7, 8)
g.addEdge(1, 7, 11)
g.addEdge(7, 8, 7)
g.addEdge(7, 6, 1)
g.addEdge(7, 1, 11)
g.addEdge(1, 2, 8)
g.addEdge(2, 3, 7)
g.addEdge(2, 5, 4)
g.addEdge(2, 8, 2)
g.addEdge(6, 8, 6)
g.addEdge(6, 5, 2)
g.addEdge(5, 2, 4)
g.addEdge(5, 3, 14)
g.addEdge(5, 4, 10)
g.addEdge(3, 4, 9)
print(g.dijsktra(0))

Current Output:

[0, 4, 15, 25, 21, 11, 9, 8, 15] # Index represents the vertex

Expected Output

[0, 4, 12, 19, 21, 11, 9, 8 ,14]

Here's the graph we are solving:

Please be aware this is not a code-writing or tutoring service. We can help solve specific, technical problems, not open-ended requests for code or advice. Please edit your question to show what you have tried so far, and what specific problem you need help with. See the How To Ask a Good Question page for details on how to best help us help you. — itprorh66
– itprorh66, Commented Feb 4, 2021 at 23:51
@itprorh66 OP provided his code, the expected output, and his output. IMHO, there is nothing wrong with this question. — Yuri Ginsburg
– Yuri Ginsburg, Commented Feb 5, 2021 at 2:53
wow, I spent hours writing the code and whiteboarding and this guy is saying I asked without researching anyway, drank some coffee and fixed it. Answering it too. — Shubham Prashar
– Shubham Prashar, Commented Feb 5, 2021 at 5:38

Shubham Prashar · Accepted Answer · 2021-02-05 05:39:50Z

2

The problem was with the function that checks the min distance, We need to update the current max so that we can compare it with other unvisited vertices and see if another vertex exists with a lesser value.

def minDist(self, dist, visited):
    max1 = 3 ** 38
    minIndex = 0
    for v in range(self.numofVertices):
        if dist[v] < max1 and v not in visited:
            max1 = dist[v]
            minIndex = v
    return minIndex

answered Feb 5, 2021 at 5:39

Shubham Prashar

10912 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user79161 Over a year ago

While I think this answer may suffice, I think it might be helpful for someone else facing the problem to be given more insight about how you arrived at solution. See if you can add more details in the answer. By the way, kudos for get the solution yourself.

Shubham Prashar Over a year ago

sure will do it after my lecture! :)

Yuri Ginsburg · Accepted Answer · 2021-02-05 05:50:24Z

0

There is an error in minDist method. It returns the index of first adjacent index, not the one with minimal distance.

This function should look like:

def minDist(self, dist, visited):
    m = INT_MAX
    for v in range(self.numofVertices):
        if dist[v] < m and v not in visited:
            m = dist[v]
            minIndex = v 
    return minIndex

Also, I am not sure that you have to assign both vertList[u] and vertList[v] in addEdge.

answered Feb 5, 2021 at 5:50

Yuri Ginsburg

2,6212 gold badges18 silver badges22 bronze badges

1 Comment

Shubham Prashar Over a year ago

Its because the edges are undirected, or let's just say they are bidirectional.

Collectives™ on Stack Overflow

Dijkstra's algorithm Python

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related