AOS 2 Psuedo Code

Question 1

Give me Prims

Answer 1

function Prim(graph, startVertex):
create a priority queue PQ
create a set to store visited vertices
create a list to store the MST edges

add startVertex to PQ with key 0

while PQ is not empty:
    u = vertex in PQ with min key
    remove u from PQ
    add u to visited set
    
    for each neighbor v of u:
        if v is not in visited and weight(u, v) < key(v):
            add v to PQ with key weight(u, v)
            set parent[v] = u

return MST edges

Question 2

Give me Dijkstra

Answer 2

function Dijkstra(graph, startVertex):
create a priority queue PQ
create a distance array dist initialized with infinity

add startVertex to PQ with distance 0
dist[startVertex] = 0

while PQ is not empty:
    u = vertex in PQ with min distance
    remove u from PQ
    
    for each neighbor v of u:
        newDist = dist[u] + weight(u, v)
        if newDist < dist[v]:
            dist[v] = newDist
            add v to PQ with distance newDist

return dist array

Question 3

Give me Bellman Fjord

Answer 3

function BellmanFord(graph, startVertex):
create a distance array dist initialized with infinity
dist[startVertex] = 0

for i from 1 to |V| - 1:
    for each edge (u, v) in graph:
        if dist[u] + weight(u, v) < dist[v]:
            dist[v] = dist[u] + weight(u, v)

for each edge (u, v) in graph:
    if dist[u] + weight(u, v) < dist[v]:
        return "Negative cycle detected"

return dist array

Question 4

Give me Floyd Warshall

Answer 4

function FloydWarshall(graph):
create a distance matrix dist initialized with infinity

for each vertex v in graph:
    dist[v][v] = 0

for each edge (u, v) in graph:
    dist[u][v] = weight(u, v)

for k from 1 to |V|:
    for i from 1 to |V|:
        for j from 1 to |V|:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

return dist matrix

Question 5

Give me Page Rank

Answer 5

function PageRank(graph, dampingFactor, maxIterations):
create a vector rank initialized with 1 / |V| for each vertex
create a vector newRank initialized with 0 for each vertex

for i from 1 to maxIterations:
    for each vertex v in graph:
        sum = 0
        for each incoming neighbor u of v:
            sum += rank[u] / outDegree(u)
        
        newRank[v] = (1 - dampingFactor) / |V| + dampingFactor * sum
    
    rank = newRank
    newRank = [0] * |V|

return rank vector