“Dijkstras Python” Kode Jawaban

Dijkstras Python

"""
This implementation takes in a single source node, and returns a dictionary
of the predecessors. The implementation of print path beneath it returns 
the Dijkstra's algorithm shortest path from the source node, to a target node.
"""

class Graph:
    def __init__(self, graph={}):
        self.graph = graph

	def Dijkstra(self, source):
      dist = {}
      pred = {}
      u = source

      unvisited = set()

      for vertex in self.graph.keys():  # Initializations
        dist[vertex] = sys.maxsize
        unvisited.add(vertex)  # All nodes initially in Q
        pred[vertex] = -1

        dist[source] = 0  # Distance from source to source is set to 0

      while len(unvisited) > 0:  # The main loop

        minDistance = sys.maxsize
        minVertex = source
        for vertex in unvisited:
          if dist[vertex] < minDistance:
            minDistance = dist[vertex]
            minVertex = vertex

            u = minVertex
            unvisited.remove(u)

            for neighborEdge in self.graph[u]:
              w = float(neighborEdge[1])
              v = neighborEdge[0]

              newLength = dist[u] + w

              if newLength < dist[v]:
                dist[v] = newLength
                pred[v] = u
		return pred
        
	def printPath(self, pred, source, target):
        path = [target]
        while path[-1] != source:
            predKey = pred.get(target)
            path.append(predKey)
            target = predKey

        path.reverse()
        # print(path)
        return path
Dylan Shade

Algoritma Dijkstra Menggunakan Python

function Dijkstra(Graph, source):
       dist[source]  := 0                     // Distance from source to source is set to 0
       for each vertex v in Graph:            // Initializations
           if v ≠ source
               dist[v]  := infinity           // Unknown distance function from source to each node set to infinity
           add v to Q                         // All nodes initially in Q

      while Q is not empty:                  // The main loop
          v := vertex in Q with min dist[v]  // In the first run-through, this vertex is the source node
          remove v from Q 

          for each neighbor u of v:           // where neighbor u has not yet been removed from Q.
              alt := dist[v] + length(v, u)
              if alt < dist[u]:               // A shorter path to u has been found
                  dist[u]  := alt            // Update distance of u 

      return dist[]
  end function
Hussain Abbas

Jawaban yang mirip dengan “Dijkstras Python”

Pertanyaan yang mirip dengan “Dijkstras Python”

Lebih banyak jawaban terkait untuk “Dijkstras Python” di Python

Jelajahi jawaban kode populer menurut bahasa

Jelajahi bahasa kode lainnya