Algoritmos

Question 1

Dijkstra

Answer 1

def dijkstra(graph, start_vertex):
D = {v:float(‘inf’) for v in range(graph.v)}
D[start_vertex] = 0

pq = PriorityQueue()
pq.put((0, start_vertex))

while not pq.empty():
    (dist, current_vertex) = pq.get()
    graph.visited.append(current_vertex)

    for neighbor in range(graph.v):
        if graph.edges[current_vertex][neighbor] != -1:
            distance = graph.edges[current_vertex][neighbor]
            if neighbor not in graph.visited:
                old_cost = D[neighbor]
                new_cost = D[current_vertex] + distance
                if new_cost < old_cost:
                    pq.put((new_cost, neighbor))
                    D[neighbor] = new_cost
return D

Question 2

Bellman Ford

Question 3

BFS

Answer 3

def bfs(self, start_node, target_node):
# Set of visited nodes to prevent loops
visited = set()
queue = Queue()

# Add the start_node to the queue and visited list
queue.put(start_node)
visited.add(start_node)

# start_node has not parents
parent = dict()
parent[start_node] = None

# Perform step 3
path_found = False
while not queue.empty():
    current_node = queue.get()
    if current_node == target_node:
        path_found = True
        break

    for (next_node, weight) in self.m_adj_list[current_node]:
        if next_node not in visited:
            queue.put(next_node)
            parent[next_node] = current_node
            visited.add(next_node)
            
# Path reconstruction
path = []
if path_found:
    path.append(target_node)
    while parent[target_node] is not None:
        path.append(parent[target_node]) 
        target_node = parent[target_node]
    path.reverse()
return path

Question 4

DFS

Answer 4

def dfs(self, start, target, path = [], visited = set()):
path.append(start)
visited.add(start)
if start == target:
return path
for (neighbour, weight) in self.m_adj_list[start]:
if neighbour not in visited:
result = self.dfs(neighbour, target, path, visited)
if result is not None:
return result
path.pop()
return None

Question 5

Kruskall root of subtree

Answer 5

Finds the root node of a subtree containing node i
def find_subtree(self, parent, i):
if parent[i] == i:
return i
return self.find_subtree(parent, parent[i])

Question 6

Kruskall conectar

Answer 6

Connects subtrees containing nodes x and y
def connect_subtrees(self, parent, subtree_sizes, x, y):
xroot = self.find_subtree(parent, x)
yroot = self.find_subtree(parent, y)
if subtree_sizes[xroot] < subtree_sizes[yroot]:
parent[xroot] = yroot
elif subtree_sizes[xroot] > subtree_sizes[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
subtree_sizes[xroot] += 1

Question 7

Kruskall kruskall

Answer 7

def kruskals_mst(self):
# Resulting tree
result = []

# Iterator
i = 0
# Number of edges in MST
e = 0

# Sort edges by their weight
self.m_graph = sorted(self.m_graph, key=lambda item: item[2])

# Auxiliary arrays
parent = []
subtree_sizes = []

# Initialize `parent` and `subtree_sizes` arrays
for node in range(self.m_num_of_nodes):
    parent.append(node)
    subtree_sizes.append(0)

# Important property of MSTs
# number of egdes in a MST is 
# equal to (m_num_of_nodes - 1)
while e < (self.m_num_of_nodes - 1):
    # Pick an edge with the minimal weight
    node1, node2, weight = self.m_graph[i]
    i = i + 1

    x = self.find_subtree(parent, node1)
    y = self.find_subtree(parent, node2)

    if x != y:
        e = e + 1
        result.append([node1, node2, weight])
        self.connect_subtrees(parent, subtree_sizes, x, y)

# Print the resulting MST
for node1, node2, weight in result:
    print("%d - %d: %d" % (node1, node2, weight))

Question 8

Floyd Warshall

Question 9

Ford Fulkerson