Dijkstra Algorithm:

Dijkstra’s Algorithm is a classic algorithm in Computer Science used to find the shortest path from a single source node. This graph can represent, for example, road networks, where intersections are nodes and roads are edges with eights (distances or costs. The algorithm assumes that all edge weights are non-negative.

The main idea is to repeatedly select the node with the smallest tentative distance, then update its neighbours. This approach guarantees that we are always processing nodes in the order of their shortest distance from the starting node.

Basic Steps:

1. Initialize: Start with a source node and initialize that distance to that node as 0. Initialize distance to all other nodes as infinity. Maintain a priority queue to select the node with the minimum tentative distance.
2. Relaxation: For each node, inspect its neighbours (nodes directly connected via edge). If the distance to the neighbour through the current node is smaller than the known distance, update the neighbour’s distance.
3. Repeat: continue this process until all nodes have been processed.
4. End Condition: At the end of the algorithm, the shortest path to all nodes from the source node will be calculated.

Template:

 public Dictionary<int,int> FindShortestDistance(int source, Dictionary<int, List<Tuple<int,int>>> graph)
 {
     var distance = new Dictionary<int, int>();
     var previousNode = new Dictionary<int, int?>();
     var queue = new PriorityQueue<int, int>();
     foreach(var node in graph.Keys)
     {
         distance[node] = int.MaxValue;
         previousNode[node] = null;
     }

     distance[source] = 0;
     queue.Enqueue(source, 0);

     while(queue.Count > 0)
     {
         queue.TryDequeue(out int currentNode, out int currentDistance);

         foreach(var neightbour in graph[currentNode])
         {
             var neighbourNode = neightbour.Item1;
             var newDistance = currentDistance + neightbour.Item2;
             if(newDistance > distance[neighbourNode])
             {
                 distance[neighbourNode] = newDistance;
                 previousNode[neighbourNode] = currentNode;
                 queue.EnqueueDequeue(neighbourNode, currentDistance);
             }
         }
     }

     return distance;
 }

Bellman-Ford:

The Bellman-Ford algorithm is used to find shortest path from a single node to all other nodes in a graph. Unlike Dijkstra’s algorithm, the Bellman-Ford can handle graphs with negative edge weights. However it cannot work with graphs that contain negative weight cycles (cycles where the sum of edge weights is negative.

The algorithm works by relaxing the edges repeatedly, relaxing an edge means updating the shortest distance to the target node of the edge, if a shorter path is found via the edge.

Step for Bellman-Ford:

1. Initialize: Set the distance to source node as 0 and set distance to all other nodes as infinity.
2. Relaxation: For each edge in a graph, if the distance to the target node through the source node is shorter than the known distance, update it.
3. Repeat: Repeat the relaxation step for all edges (V-1) times.
4. Negative weight cycle checks: After V-1 iterations, perform one more relaxation for al edges, if any distance is updated, it indicates a negative weight cycle.

Template:

public int[] Bellman(List<Edge> edges, int vertices, int source)
{
    var distance = new int[vertices+1];
    Array.Fill(distance, int.MaxValue);
    distance[source] = 0;

    //relaxing v-1 times
    for(int i = 0; i < vertices; i++)
    {
        foreach(var edge in edges)
        {
            if (distance[edge.Source] != int.MaxValue && distance[source] + edge.Weight < distance[edge.Destination])
            {
                distance[edge.Destination] = distance[source] + edge.Weight;
            }
        }
    }

    // relaxing one more time to check for negative edge weight cycle
    foreach (var edge in edges)
    {
        if (distance[edge.Source] != int.MaxValue && distance[source] + edge.Weight < distance[edge.Destination])
        {
            throw new InvalidOperationException("negative-weight cycle");
        }
    }
    return distance;
}

Detailed explanation on edge relaxation:

Why Relax Edges V-1 Times?

Imagine a situation where you're trying to find the shortest path from a starting point (source node) to all other nodes in a graph. If all edges have positive weights, each time you "relax" an edge, you may update the shortest path to a node. However, if there are negative weights, the shortest path to a node might not be immediately obvious, and it could take a few iterations (or relaxations) to update the shortest path correctly.

Here's why we relax edges V−1 times:

1. Shortest Path Length:

• A shortest path from the source to any node can have at most V-1 edges. This is because in a graph with VVV nodes, the longest possible path you can have between two nodes (without visiting the same node twice) has V−1 edges.
  For example:

• If you have 5 nodes (let’s say V=5), the longest possible path between the source and any other node can have at most 4 edges.

2. Relaxing Once Isn’t Enough:

• In the first pass (the first *relaxation), you may only find the shortest path to nodes that are directly connected to the source node (nodes that can be reached with just one edge).
• After the second pass, you can find the shortest paths to nodes that are 2 edges away, and so on.
• Each time you relax the edges, you are allowing paths that take more edges to get closer to the correct shortest path.

3. Why V-1 Relaxations?:

• You need to perform V-1 relaxations to ensure that the shortest paths to all nodes are correctly calculated. This is because the farthest node from the source in terms of edges could be reached in exactly V-1 steps (assuming the graph doesn't contain cycles or negative weight cycles).
• After V-1 relaxations, you will have visited all possible paths that could have taken you through up to V-1 edges.

4. Why not more than V-1 Relaxations?

• If you relax edges more than V-1 times, that means you’re still able to update the shortest distance to a node. This suggests that there’s a negative weight cycle somewhere in the graph, because a negative cycle would allow you to continually reduce the distance to a node indefinitely by traversing the cycle repeatedly.

Summary:
• Relaxing an edge means checking if the shortest distance to a destination node can be improved by going through a source node.
• We relax edges V-1 times because the longest shortest path from the source node to any other node can have at most V-1 edges. After V-1 relaxations, all the shortest paths should be correctly computed.
• If any edge can still be relaxed after V-1 iterations, it indicates the presence of a negative-weight cycle in the graph.

Floyd-Warshall:

The floydd warshall is a dynamic programming algorithm used to find the shortest path between all pairs of vertices in a weighted graph. It can handle both directed and undirected graphs.
It works if there are negative edge weights but no negative edge weight cycle.

How it works?
Imagine you have a graph where the nodes represents the places and edges represent the paths between those two places. The algorithm does this by considering every possible “intermediate” node and checks if a path through that node offers a shorter distance between two other nodes.

The algorithm maintains a matrix dist[][] where dist[i][j] represents the shortest path / distance from node I to node j. Initially the matrix is set to edge weights, and for nodes without a direct edge the matrix is set to infinity. The algorithm than iteratively updates the matrix considering each node as intermediate node.

Steps:

1. Initialization: Start with a distance matrix dist[i][j]. If there is a direct edge between I and j, initialuze dis[i][j] with edge weight. If there is no direct edge initialize it with infinity. The diagonal will be set to 0;
2. Update the matrix: for each intermediate node k, check if a path from I to through k is shorter than the direct path from I to j, if yes than update.
   dist[I,j] = Math.Min(dist[I,j] + dist[I,k]+dist[k][j])
3. Do this for all the nodes, considering each node as an intermediate node.

Template:

public int[,] RunFloyddWarshall(int[,] graph)
 {
     int n = graph.GetLength(0);
     var dist = new int[n,n];
            
     //Initialize the distance matrix with graph weights
     for(int i = 0; i < n; i++)
     {
         for(int j = 0; j < n; j++)
         {
             if(i == j)
             {
                 dist[i, j] = 0;
             }
             else if (graph[i,j] != 0)
             {
                 dist[i, j] = graph[i,j];
             }
             else
             {
                 dist[i, j] = int.MaxValue;
             }
         }
     }

     for(int k = 0; k < n; k++)
     {
         for(int i = 0; i < n; i++)
         {
             for(int j = 0; j < n; j++)
             {
                 if (dist[i,k] != int.MaxValue && dist[k,j] != int.MaxValue &&
                     dist[i,k] + dist[k,j] < dist[i, j])
                 {
                     dist[i, j] = dist[i, k] + dist[k, j];
                 }
             }
         }
     }

     return dist;
 }

Prim’s Algorithm:

It is a greedy algorithm that is used to find the minimum spanning tree of a weighted, undirected graph. The algorithm works by starting with an arbitrary vertex and growing the MST one edge at a time by always choosing the minimum weight edge that connects a vertex in the MST to a Vertex outside the MST.

The algorithm can be summarized as follows:

1. Initialize: Start with an arbitrary vertex and include it in the MST. Mark it as visited.
2. Select the minimum weight edge: Among the edges that connect a vertex inside the MST to a vertex outside the MST, select the edge with the minimum weight.
3. Add the edge to the MST: include the selected edge in the MST and add the connected vertex to the MST set.
4. Repeat: Repeat 2 and 3 until all vertices are included in the MST.

Key Concept:
MST: A subset of edges that connects all the vertices in the graph without any cycles and with the minimum possible total edge weight.
Greedy Choice Property: Prim’s algorithm is greedy because at each step it chooses the minimum weighted edge which connected the MST to the rest of the graph.

Template:

public int RunPrim(int vertices, List<Edge>[] graph)
 {
     // Exactly like Dijkstra
     var queue = new PriorityQueue<int, int>();
     var inMst = new bool[vertices];
     queue.Enqueue(0, 0);
     int totalWeight = 0;

     while(queue.Count > 0)
     {
         queue.TryDequeue(out var node, out var weight);
         if (inMst[node]) continue;
         inMst[node] = true;
         totalWeight += weight;
         foreach(var neighbour in graph[node])
         {
             if (!inMst[neighbour.Destination])
             {
                 queue.Enqueue(neighbour.Destination, neighbour.Weight);
             }
         }
     }

     return totalWeight;
 }

Kruskals Algorithm:

Kruskal’s algorithm is a greedy algorithm used to find the MST of a connected, undirected graph. The minimum spanning tree is a subgraph or a subset of edges that connects all the vertices and don’t form any cycles with the minimum total edge weight possible.

Steps:

1. Sort all the edges in ascending order of their weights
2. Pick the smallest edge. Check if including it in MST forms a cycle:
   a. If it does not form a cycle, add it to MST
   b. It if forms a cycle ,discard the edge``
3. Repeat step 2 until there are V-1 edges in the MST, where v is the number of vertices.
4. The result is the minimum spanning tree.

Key Concepts:

1. Cycle detection: Kruskal’s algorithm uses DSU data structure to efficiently detect cycles when adding the edge to the MST. The Union find helps track which vertices are connected.
2. Greedy Choice: Always choose the edge with the smallest weight, and ensure that it doesn’t forms a cycle when added.

Template:

using System;
using System.Collections.Generic;

class Kruskal
{
    // Union-Find (Disjoint Set) class
    public class UnionFind
    {
        private int[] parent, rank;

        public UnionFind(int size)
        {
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++)
            {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int Find(int u)
        {
            if (parent[u] != u)
                parent[u] = Find(parent[u]);  // Path compression
            return parent[u];
        }

        public void Union(int u, int v)
        {
            int rootU = Find(u);
            int rootV = Find(v);

            if (rootU != rootV)
            {
                // Union by rank
                if (rank[rootU] > rank[rootV])
                    parent[rootV] = rootU;
                else if (rank[rootU] < rank[rootV])
                    parent[rootU] = rootV;
                else
                {
                    parent[rootV] = rootU;
                    rank[rootU]++;
                }
            }
        }
    }

    // Edge class to represent an edge (u, v) with weight w
    public class Edge
    {
        public int u, v, weight;

        public Edge(int u, int v, int weight)
        {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }

    // Function to perform Kruskal's Algorithm
    public static List<Edge> KruskalMST(int vertices, List<Edge> edges)
    {
        // Sort edges by weight
        edges.Sort((e1, e2) => e1.weight.CompareTo(e2.weight));

        UnionFind uf = new UnionFind(vertices);
        List<Edge> mst = new List<Edge>();

        foreach (var edge in edges)
        {
            int u = edge.u;
            int v = edge.v;

            // If u and v are in different sets, include the edge in the MST
            if (uf.Find(u) != uf.Find(v))
            {
                uf.Union(u, v);
                mst.Add(edge);
            }
        }

        return mst;
    }

    public static void Main()
    {
        // Example usage
        int vertices = 4;
        List<Edge> edges = new List<Edge>
        {
            new Edge(0, 1, 10),
            new Edge(0, 2, 6),
            new Edge(0, 3, 5),
            new Edge(1, 3, 15),
            new Edge(2, 3, 4)
        };

        List<Edge> mst = KruskalMST(vertices, edges);

        Console.WriteLine("Edges in the Minimum Spanning Tree:");
        foreach (var edge in mst)
        {
            Console.WriteLine($"{edge.u} - {edge.v} : {edge.weight}");
        }
    }
}