7.a) Utkereso algoritmusok

Legrovidebb ut feladatok

Dijkstra

futasido: $O(n^2)$ naivan, $O((n+m)\log n)$ binaris kupaccal.

def dijkstra(G, s):
  # Initialize distances and visited set
  dist = {v: float('inf') for v in G.vertices()}
  dist[s] = 0
  visited = set()
  parent = {s: s}
 
  # Priority queue of unvisited vertices
  unvisited = set(G.vertices())
 
  while len(unvisited) > 0:
    # Find vertex with minimum distance
    u = min(unvisited, key=lambda v: dist[v])  # use heap instead
    unvisited.remove(u)
    visited.add(u)
 
    # Update distances to neighbors
    for v in G.neighbors(u):
      if v in unvisited:
        new_dist = dist[u] + G.edge_weight(u, v)
        if new_dist < dist[v]:
          dist[v] = new_dist
          parent[v] = u
 
  return dist, parent

Bellman-Ford

$O(n\cdot m)$

def BF(G, c):
  p = [0 for _ in range(n)]
  dist = [float('inf') for _ in range(n)]
  p[s], dist[s] = s, 0
  for i in range(n - 1):
    for u in range(n):
	  for v in u.neighbors():
	    if dist[u] + c(u, v) < dist[v]:
		  dist[v] = dist[u] + c(u, v)
		  p[v] = u
 
  # test if change happens after n-1 iterations, if so, non conservative weights
  for u in range(n):
    for v in u.neighbors():
	  if dist[u] + c(u, v) < dist[v]:
	    p[v] = u
		return "non conservative", K, p, v
  return "conservative", K, p, s

Kereses

Binaris kereses rendezett tombben $O(\log n)$

def binary_search(arr, val):
  left, right = 0, len(arr) - 1
  while left <= right:
    middle = (left + right) // 2
	if arr[middle] == val:
	  return middle
	elif arr[middle] < val:
	  left = middle + 1
	else:
	  right = middle - 1
  return -1  # not found

BFS $O(|V|+|E|)$

def bfs(graph, start):
  visited = set()
  queue = deque([start])
  visited.add(start)
  while queue:
    node = queue.popleft()
	print(node, end=" ")
	for neighbor in graph[node]:
	  if neighbor not in visited:
	    visited.add(neighbor)
		queue.append(neighbor)

DFS $O(|V|+|E|)$

def dfs(graph, node, visited=None):
  if visited is None:
    visited = set()
  if node not in visited:
    visited.add(node)
    print(node, end=" ")
    for neighbor in graph[node]:
	  dfs(graph, neighbor, visited)