Algoritmo de Dijkstra para un ejemplo de código de Python de gráfico completamente conectado

Recabamos por distintos sitios para así tener para ti la respuesta a tu problema, si tienes alguna inquietud deja la duda y te responderemos sin falta.

Ejemplo: Python del algoritmo de dijkstra

import sys

classVertex:def__init__(self, node):
        self.id= node
        self.adjacent =# Set distance to infinity for all nodes
        self.distance = sys.maxint
        # Mark all nodes unvisited        
        self.visited =False# Predecessor
        self.previous =Nonedefadd_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor]= weight

    defget_connections(self):return self.adjacent.keys()defget_id(self):return self.iddefget_weight(self, neighbor):return self.adjacent[neighbor]defset_distance(self, dist):
        self.distance = dist

    defget_distance(self):return self.distance

    defset_previous(self, prev):
        self.previous = prev

    defset_visited(self):
        self.visited =Truedef__str__(self):returnstr(self.id)+' adjacent: '+str([x.idfor x in self.adjacent])classGraph:def__init__(self):
        self.vert_dict =
        self.num_vertices =0def__iter__(self):returniter(self.vert_dict.values())defadd_vertex(self, node):
        self.num_vertices = self.num_vertices +1
        new_vertex = Vertex(node)
        self.vert_dict[node]= new_vertex
        return new_vertex

    defget_vertex(self, n):if n in self.vert_dict:return self.vert_dict[n]else:returnNonedefadd_edge(self, frm, to, cost =0):if frm notin self.vert_dict:
            self.add_vertex(frm)if to notin self.vert_dict:
            self.add_vertex(to)

        self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
        self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)defget_vertices(self):return self.vert_dict.keys()defset_previous(self, current):
        self.previous = current

    defget_previous(self, current):return self.previous

defshortest(v, path):''' make shortest path from v.previous'''if v.previous:
        path.append(v.previous.get_id())
        shortest(v.previous, path)returnimport heapq

defdijkstra(aGraph, start, target):print'''Dijkstra's shortest path'''# Set the distance for the start node to zero 
    start.set_distance(0)# Put tuple pair into the priority queue
    unvisited_queue =[(v.get_distance(),v)for v in aGraph]
    heapq.heapify(unvisited_queue)whilelen(unvisited_queue):# Pops a vertex with the smallest distance 
        uv = heapq.heappop(unvisited_queue)
        current = uv[1]
        current.set_visited()#for next in v.adjacent:fornextin current.adjacent:# if visited, skipifnext.visited:continue
            new_dist = current.get_distance()+ current.get_weight(next)if new_dist <next.get_distance():next.set_distance(new_dist)next.set_previous(current)print'updated : current = %s next = %s new_dist = %s' 
                        %(current.get_id(),next.get_id(),next.get_distance())else:print'not updated : current = %s next = %s new_dist = %s' 
                        %(current.get_id(),next.get_id(),next.get_distance())# Rebuild heap# 1. Pop every itemwhilelen(unvisited_queue):
            heapq.heappop(unvisited_queue)# 2. Put all vertices not visited into the queue
        unvisited_queue =[(v.get_distance(),v)for v in aGraph ifnot v.visited]
        heapq.heapify(unvisited_queue)if __name__ =='__main__':

    g = Graph()

    g.add_vertex('a')
    g.add_vertex('b')
    g.add_vertex('c')
    g.add_vertex('d')
    g.add_vertex('e')
    g.add_vertex('f')

    g.add_edge('a','b',7)  
    g.add_edge('a','c',9)
    g.add_edge('a','f',14)
    g.add_edge('b','c',10)
    g.add_edge('b','d',15)
    g.add_edge('c','d',11)
    g.add_edge('c','f',2)
    g.add_edge('d','e',6)
    g.add_edge('e','f',9)print'Graph data:'for v in g:for w in v.get_connections():
            vid = v.get_id()
            wid = w.get_id()print'( %s , %s, %3d)'%( vid, wid, v.get_weight(w))

    dijkstra(g, g.get_vertex('a'), g.get_vertex('e')) 

    target = g.get_vertex('e')
    path =[target.get_id()]
    shortest(target, path)print'The shortest path : %s'%(path[::-1])

Si conservas alguna perplejidad o capacidad de medrar nuestro post te invitamos añadir una crónica y con deseo lo leeremos.

---

---

Utiliza Nuestro Buscador