A complete Guide to Important Algorithms In DSA

Posted by tintin_2003 on 2025-11-20 09:14:41 |

Share: Facebook | Twitter | Whatsapp | Linkedin Visits: 85

1) Linear Search

{short text rich description}
Linear search scans each element in sequence until it finds the target. Best for small lists or unsorted arrays. It's simple, stable, and needs no preprocessing.

{code in C language}

#include <stdio.h>
#define MAX 100

int linear_search(int arr[], int n, int key){
    for(int i=0;i<n;i++){
        if(arr[i]==key) return i; // return index
    }
    return -1;
}

int main(){
    int arr[] = {5, 2, 9, 1, 6};
    int n = 5;
    int key = 1;
    int idx = linear_search(arr,n,key);
    if(idx>=0) printf("Found %d at index %d\n", key, idx);
    else printf("Not found\n");
    return 0;
}

{their time and space complexity}

• Time: O(n) worst-case and average. Best O(1) if first element.

• Space: O(1).

{output and dry run of the output}
Sample output:

Found 1 at index 3

Dry run: check indices 0→5: arr[0]=5 ≠1; arr[1]=2 ≠1; arr[2]=9 ≠1; arr[3]=1 → match, return index 3.

2) Binary Search

{short text rich description}
Binary search finds a key in a sorted array by repeatedly halving the search interval. Very efficient for read-only sorted lists.

{code in C language}

#include <stdio.h>

int binary_search(int arr[], int n, int key){
    int l=0, r=n-1;
    while(l<=r){
        int mid = (l + r) / 2;
        if(arr[mid]==key) return mid;
        else if(arr[mid] < key) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

int main(){
    int arr[] = {1,2,4,5,7,9};
    int n = 6;
    int key = 5;
    int idx = binary_search(arr,n,key);
    if(idx>=0) printf("Found %d at index %d\n", key, idx);
    else printf("Not found\n");
    return 0;
}

{their time and space complexity}

• Time: O(log n).

• Space: O(1).

{output and dry run of the output}
Sample output:

Found 5 at index 3

Dry run: mid=(0+5)/2=2 -> arr[2]=4 <5 → l=3; mid=(3+5)/2=4 -> arr[4]=7 >5 → r=3; mid=3 -> arr[3]=5 → found index 3.

3) Insertion Sort

{short text rich description}
Builds sorted array one element at a time by inserting each element into its correct position among prior elements. Good for small arrays and nearly-sorted data.

{code in C language}

#include <stdio.h>

void insertion_sort(int arr[], int n){
    for(int i=1;i<n;i++){
        int key = arr[i];
        int j = i-1;
        while(j>=0 && arr[j] > key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

int main(){
    int arr[] = {5,2,9,1,6};
    int n = 5;
    insertion_sort(arr,n);
    for(int i=0;i<n;i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

{their time and space complexity}

• Time: O(n^2) worst-case; O(n) best-case (already sorted).

• Space: O(1).

{output and dry run of the output}
Sample output:

1 2 5 6 9

Dry run: Insert 2 before 5 -> [2,5,9,1,6]; then insert 9 after 5 -> [2,5,9,1,6]; insert 1 → [1,2,5,9,6]; insert 6 → [1,2,5,6,9].

4) Selection Sort

{short text rich description}
Repeatedly selects the smallest (or largest) item from unsorted portion and swaps it with start of unsorted portion. Simple but not stable or efficient for large lists.

{code in C language}

#include <stdio.h>

void selection_sort(int arr[], int n){
    for(int i=0;i<n-1;i++){
        int min_idx = i;
        for(int j=i+1;j<n;j++){
            if(arr[j] < arr[min_idx]) min_idx = j;
        }
        if(min_idx != i){
            int t = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = t;
        }
    }
}

int main(){
    int arr[] = {64,25,12,22,11};
    int n = 5;
    selection_sort(arr,n);
    for(int i=0;i<n;i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

{their time and space complexity}

• Time: O(n^2) always.

• Space: O(1).

{output and dry run of the output}
Sample output:

11 12 22 25 64

Dry run: find min in whole array -> 11 swap with first; find min in remaining -> 12 swap with second; etc.

5) Bubble Sort

{short text rich description}
Repeatedly swaps adjacent elements if out of order. Works by "bubbling" largest elements to the end. Simple but inefficient.

{code in C language}

#include <stdio.h>
#include <stdbool.h>

void bubble_sort(int arr[], int n){
    for(int pass=0; pass<n-1; pass++){
        bool swapped = false;
        for(int i=0;i<n-1-pass;i++){
            if(arr[i] > arr[i+1]){
                int t = arr[i]; arr[i] = arr[i+1]; arr[i+1] = t;
                swapped = true;
            }
        }
        if(!swapped) break; // already sorted
    }
}

int main(){
    int arr[] = {5,1,4,2,8};
    int n = 5;
    bubble_sort(arr,n);
    for(int i=0;i<n;i++) printf("%d ",arr[i]);
    printf("\n");
    return 0;
}

{their time and space complexity}

• Time: O(n^2) worst/average, O(n) best (with early exit).

• Space: O(1).

{output and dry run of the output}
Sample output:

1 2 4 5 8

Dry run: adjacent swaps repeatedly move larger values rightward until sorted.

6) Merge Sort

{short text rich description}
Divide-and-conquer: split array, sort halves, merge sorted halves. Stable and O(n log n), but requires extra temporary array.

{code in C language}

#include <stdio.h>
#define MAX 100

void merge(int a[], int l, int m, int r){
    int temp[MAX];
    int i=l, j=m+1, k=0;
    while(i<=m && j<=r){
        if(a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while(i<=m) temp[k++] = a[i++];
    while(j<=r) temp[k++] = a[j++];
    for(i=l, k=0; i<=r; i++, k++) a[i] = temp[k];
}

void merge_sort(int a[], int l, int r){
    if(l>=r) return;
    int m = (l + r) / 2;
    merge_sort(a, l, m);
    merge_sort(a, m+1, r);
    merge(a, l, m, r);
}

int main(){
    int a[] = {12,11,13,5,6,7};
    int n = 6;
    merge_sort(a,0,n-1);
    for(int i=0;i<n;i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

{their time and space complexity}

• Time: O(n log n) always.

• Space: O(n) extra for merging (we used temp array).

{output and dry run of the output}
Sample output:

5 6 7 11 12 13

Dry run: split repeatedly to single elements, merge pairs: [12],[11] -> [11,12], etc., final merged sorted array.

7) Quick Sort

{short text rich description}
Divide-and-conquer using a pivot; partition elements less/greater than pivot, then sort partitions. Excellent average performance; worst-case O(n^2) for bad pivots.

{code in C language}

#include <stdio.h>

int partition(int a[], int l, int r){
    int pivot = a[r];
    int i = l - 1;
    for(int j=l;j<r;j++){
        if(a[j] <= pivot){
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    int t = a[i+1]; a[i+1] = a[r]; a[r] = t;
    return i+1;
}

void quick_sort(int a[], int l, int r){
    if(l < r){
        int p = partition(a,l,r);
        quick_sort(a,l,p-1);
        quick_sort(a,p+1,r);
    }
}

int main(){
    int a[] = {10,7,8,9,1,5};
    int n = 6;
    quick_sort(a,0,n-1);
    for(int i=0;i<n;i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

{their time and space complexity}

• Time: Average O(n log n), worst O(n^2).

• Space: O(log n) average recursion depth; O(n) worst recursion depth (if unbalanced).

{output and dry run of the output}
Sample output:

1 5 7 8 9 10

Dry run: choose last element as pivot, partition array around pivot, recurse.

8) Binary Search Tree (BST) — array-based implementation (no pointers)

{short text rich description}
A BST stores values with left child < node < right child. Here we implement BST using arrays: val[], left[], right[], and root is index of root. This avoids pointers/structs.

{code in C language}

#include <stdio.h>
#define MAX 100
#define NIL -1

int val[MAX];
int left_idx[MAX];
int right_idx[MAX];
int root = NIL;
int next_free = 0;

int new_node(int x){
    if(next_free >= MAX) return NIL;
    val[next_free] = x;
    left_idx[next_free] = NIL;
    right_idx[next_free] = NIL;
    return next_free++;
}

void bst_insert(int x){
    if(root == NIL){
        root = new_node(x);
        return;
    }
    int cur = root;
    int parent = NIL;
    while(cur != NIL){
        parent = cur;
        if(x < val[cur]) cur = left_idx[cur];
        else cur = right_idx[cur];
    }
    int node = new_node(x);
    if(x < val[parent]) left_idx[parent] = node;
    else right_idx[parent] = node;
}

int bst_search(int x){
    int cur = root;
    while(cur != NIL){
        if(val[cur] == x) return cur;
        if(x < val[cur]) cur = left_idx[cur];
        else cur = right_idx[cur];
    }
    return NIL;
}

void inorder(int cur){
    if(cur == NIL) return;
    inorder(left_idx[cur]);
    printf("%d ", val[cur]);
    inorder(right_idx[cur]);
}

int main(){
    int keys[] = {50,30,20,40,70,60,80};
    int n = 7;
    for(int i=0;i<n;i++) bst_insert(keys[i]);
    printf("Inorder: ");
    inorder(root);
    printf("\n");
    int s = 60;
    int idx = bst_search(s);
    if(idx!=NIL) printf("Found %d at index %d\n", s, idx);
    else printf("%d not found\n", s);
    return 0;
}

{their time and space complexity}

• Time: Search/insert average O(log n) for balanced tree, worst O(n).

• Space: O(n) for arrays.

{output and dry run of the output}
Sample output:

Inorder: 20 30 40 50 60 70 80 
Found 60 at index 5

Dry run: Insert 50 as root. Insert 30 -> left of 50. Insert 20 -> left of 30. Insert 40 -> right of 30. Insert 70 -> right of 50. Insert 60 -> left of 70. Insert 80 -> right of 70. Inorder traversal prints sorted order.

9) Heap / Heapsort (array-based)

{short text rich description}
A binary heap is a complete binary tree stored in an array; parent-child index relations: parent i -> children 2i+1, 2i+2. Heapsort builds a max-heap and repeatedly extracts max to sort in O(n log n).

{code in C language}

#include <stdio.h>
#define MAX 100

void heapify(int a[], int n, int i){
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;
    if(l < n && a[l] > a[largest]) largest = l;
    if(r < n && a[r] > a[largest]) largest = r;
    if(largest != i){
        int t = a[i]; a[i] = a[largest]; a[largest] = t;
        heapify(a,n,largest);
    }
}

void build_max_heap(int a[], int n){
    for(int i = n/2 -1; i>=0; i--) heapify(a,n,i);
}

void heapsort(int a[], int n){
    build_max_heap(a,n);
    for(int i = n-1; i>0; i--){
        int t = a[0]; a[0] = a[i]; a[i] = t; // move max to end
        heapify(a,i,0);
    }
}

int main(){
    int a[] = {12,11,13,5,6,7};
    int n = 6;
    heapsort(a,n);
    for(int i=0;i<n;i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

{their time and space complexity}

• Time: O(n log n) worst/average.

• Space: O(1) additional (in-place).

{output and dry run of the output}
Sample output:

5 6 7 11 12 13

Dry run: build max heap (root holds max), swap root with last, reduce heap size, heapify root, repeat.

10) Priority Queue (insert, delete, change key) — min-heap array-based

{short text rich description}
Priority queue implemented as a min-heap stored in an array. Supports insert, extract_min, and decrease_key operations without pointers.

{code in C language}

#include <stdio.h>
#define MAX 100
int heap[MAX];
int heap_size = 0;

void swap(int *a, int *b){ int t=*a; *a=*b; *b=t; }

void heap_insert(int x){
    if(heap_size >= MAX) return;
    int i = heap_size++;
    heap[i] = x;
    while(i != 0){
        int p = (i-1)/2;
        if(heap[p] <= heap[i]) break;
        swap(&heap[p], &heap[i]);
        i = p;
    }
}

int extract_min(){
    if(heap_size <= 0) return -1;
    int root = heap[0];
    heap[0] = heap[--heap_size];
    // heapify down
    int i=0;
    while(1){
        int l=2*i+1, r=2*i+2, smallest=i;
        if(l < heap_size && heap[l] < heap[smallest]) smallest = l;
        if(r < heap_size && heap[r] < heap[smallest]) smallest = r;
        if(smallest == i) break;
        swap(&heap[i], &heap[smallest]);
        i = smallest;
    }
    return root;
}

// decrease key at index i to new_val (assumes new_val <= heap[i])
void decrease_key(int i, int new_val){
    if(i<0 || i>=heap_size) return;
    heap[i] = new_val;
    while(i!=0){
        int p=(i-1)/2;
        if(heap[p] <= heap[i]) break;
        swap(&heap[p], &heap[i]);
        i = p;
    }
}

int main(){
    heap_insert(5);
    heap_insert(3);
    heap_insert(17);
    heap_insert(10);
    heap_insert(84);
    heap_insert(19);
    heap_insert(6);
    heap_insert(22);
    heap_insert(9);
    printf("Extract min: %d\n", extract_min()); // should be 3
    // Example decrease key at index 2 -> set to 1 (if index valid)
    if(heap_size > 2) decrease_key(2, 1);
    printf("Extract min: %d\n", extract_min()); // may be 1
    return 0;
}

{their time and space complexity}

• Insert: O(log n). Extract min: O(log n). Decrease key: O(log n).

• Space: O(n).

{output and dry run of the output}
Sample output (one possible result depending on internal indices):

Extract min: 3
Extract min: 1

Dry run: insert keeps heap property; extract removes min at root, moves last element to root then heapifies down.

11) BFS (Breadth-First Search) — adjacency matrix

{short text rich description}
BFS explores graph layer by layer using a queue; finds shortest path in unweighted graphs (by edges). Implemented with arrays and queue indices.

{code in C language}

#include <stdio.h>
#define MAXV 10

int adj[MAXV][MAXV]; // adjacency matrix
int visited[MAXV];
int queue[MAXV];
int front, back;

void bfs(int n, int start){
    for(int i=0;i<n;i++) visited[i]=0;
    front = back = 0;
    queue[back++] = start; visited[start]=1;
    while(front < back){
        int u = queue[front++];
        printf("%d ", u);
        for(int v=0; v<n; v++){
            if(adj[u][v] && !visited[v]){
                visited[v] = 1;
                queue[back++] = v;
            }
        }
    }
}

int main(){
    int n = 6;
    // Example graph (undirected)
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) adj[i][j]=0;
    adj[0][1]=adj[1][0]=1;
    adj[0][2]=adj[2][0]=1;
    adj[1][3]=adj[3][1]=1;
    adj[2][4]=adj[4][2]=1;
    adj[3][5]=adj[5][3]=1;
    printf("BFS from 0: ");
    bfs(n,0);
    printf("\n");
    return 0;
}

{their time and space complexity}

• Time: O(n^2) with adjacency matrix (or O(n + m) with adjacency list).

• Space: O(n^2) for adjacency matrix.

{output and dry run of the output}
Sample output:

BFS from 0: 0 1 2 3 4 5 

Dry run: Visit 0, enqueue neighbors 1 and 2; then visit 1, enqueue 3; visit 2, enqueue 4; visit 3 -> enqueue 5; etc.

12) DFS (Depth-First Search) — adjacency matrix, iterative (stack)

{short text rich description}
DFS explores as deep as possible along a branch before backtracking. Using an explicit stack avoids recursion and pointers.

{code in C language}

#include <stdio.h>
#define MAXV 10

int adj[MAXV][MAXV];
int visited[MAXV];
int stack[MAXV];
int top;

void dfs(int n, int start){
    for(int i=0;i<n;i++) visited[i]=0;
    top = 0;
    stack[top++] = start;
    while(top){
        int u = stack[--top];
        if(visited[u]) continue;
        visited[u] = 1;
        printf("%d ", u);
        // push neighbors in reverse order to mimic recursive DFS order
        for(int v = n-1; v>=0; v--){
            if(adj[u][v] && !visited[v]) stack[top++] = v;
        }
    }
}

int main(){
    int n = 6;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) adj[i][j]=0;
    adj[0][1]=adj[1][0]=1;
    adj[0][2]=adj[2][0]=1;
    adj[1][3]=adj[3][1]=1;
    adj[2][4]=adj[4][2]=1;
    adj[3][5]=adj[5][3]=1;
    printf("DFS from 0: ");
    dfs(n,0);
    printf("\n");
    return 0;
}

{their time and space complexity}

• Time: O(n^2) with adjacency matrix.

• Space: O(n^2) adjacency matrix + O(n) stack.

{output and dry run of the output}
Sample output (order depends on neighbor iteration):

DFS from 0: 0 1 3 5 2 4 

Dry run: Start 0, push neighbors 2 and 1; pop 1 -> visit 1 -> push 3; pop 3 -> visit 3 -> push 5; etc.

13) Topological Sorting (Kahn’s algorithm) — adjacency matrix

{short text rich description}
Topological sort orders vertices of a DAG so that for every directed edge u→v, u comes before v. Kahn’s algorithm removes nodes with in-degree 0 iteratively.

{code in C language}

#include <stdio.h>
#define MAXV 20

int adj[MAXV][MAXV];
int indeg[MAXV];
int q[MAXV];
int front, back;

void topological_sort(int n){
    for(int i=0;i<n;i++) indeg[i]=0;
    for(int u=0; u<n; u++)
        for(int v=0; v<n; v++)
            if(adj[u][v]) indeg[v]++;
    front = back = 0;
    for(int i=0;i<n;i++) if(indeg[i]==0) q[back++] = i;
    int count = 0;
    while(front < back){
        int u = q[front++];
        printf("%d ", u);
        count++;
        for(int v=0; v<n; v++){
            if(adj[u][v]){
                indeg[v]--;
                if(indeg[v]==0) q[back++] = v;
            }
        }
    }
    if(count != n) printf("\nGraph has a cycle\n");
    else printf("\n");
}

int main(){
    int n = 6;
    int i;
    for(i=0;i<n;i++) for(int j=0;j<n;j++) adj[i][j]=0;
    // example DAG edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1
    adj[5][2]=1; adj[5][0]=1; adj[4][0]=1; adj[4][1]=1;
    adj[2][3]=1; adj[3][1]=1;
    printf("Topological order: ");
    topological_sort(n);
    return 0;
}

{their time and space complexity}

• Time: O(n^2) with adjacency matrix. (O(n+m) with adjacency list.)

• Space: O(n^2) for adjacency matrix.

{output and dry run of the output}
Sample output (one valid order):

Topological order: 4 5 2 3 1 0 

Dry run: indeg calc -> nodes with indeg 0 pushed (4,5) -> pop 4 -> reduce indeg of 0,1 -> etc.

14) Kruskal’s Algorithm (Minimum Spanning Tree) — edge list + union-find arrays

{short text rich description}
Kruskal sorts edges by weight and adds edges that don’t form cycles, using union-find (disjoint set) for cycle detection. We implement union-find with arrays parent[] and rank[].

{code in C language}

#include <stdio.h>
#define MAXV 20
#define MAXE 100

int parent[MAXV];
int rank_arr[MAXV];

void make_set(int n){
    for(int i=0;i<n;i++){ parent[i]=i; rank_arr[i]=0; }
}

int find_set(int v){
    while(parent[v] != v) v = parent[v];
    return v;
}

void union_sets(int a, int b){
    a = find_set(a); b = find_set(b);
    if(a==b) return;
    if(rank_arr[a] < rank_arr[b]) parent[a]=b;
    else if(rank_arr[a] > rank_arr[b]) parent[b]=a;
    else { parent[b]=a; rank_arr[a]++; }
}

typedef struct { int u,v,w; } Edge; // using struct only locally in code: if you strictly forbid structs remove and use arrays - but keeping tiny struct here for clarity

int main(){
    int n = 4; // vertices 0..3
    Edge edges[] = { {0,1,10},{0,2,6},{0,3,5},{1,3,15},{2,3,4} };
    int m = 5;
    // simple sort edges by weight (selection sort)
    for(int i=0;i<m-1;i++){
        int min=i;
        for(int j=i+1;j<m;j++) if(edges[j].w < edges[min].w) min=j;
        if(min != i){ Edge t = edges[i]; edges[i]=edges[min]; edges[min]=t; }
    }
    make_set(n);
    int mst_weight = 0;
    printf("Edges in MST:\n");
    for(int i=0;i<m;i++){
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if(find_set(u) != find_set(v)){
            union_sets(u,v);
            printf("%d - %d (w=%d)\n", u, v, w);
            mst_weight += w;
        }
    }
    printf("Total weight = %d\n", mst_weight);
    return 0;
}

Note: I used a tiny Edge struct for readability in the code above. If you require absolutely no structs, we can instead store three arrays edge_u[], edge_v[], edge_w[] and sort them together; tell me and I’ll replace.

{their time and space complexity}

• Time: Sorting edges O(m log m) (here selection sort O(m^2) used for simplicity), union-find operations nearly O(α(n)). Overall O(m log m).

• Space: O(m + n).

{output and dry run of the output}
Sample output:

Edges in MST:
2 - 3 (w=4)
0 - 3 (w=5)
0 - 1 (w=10)
Total weight = 19

Dry run: sorted edges by weight: (2,3,4),(0,3,5),(0,2,6),(0,1,10),(1,3,15). Pick (2,3) add; pick (0,3) add; pick (0,2) would create cycle skip; pick (0,1) add. Done.

15) Prim’s Algorithm (adjacency matrix)

{short text rich description}
Prim grows MST by starting from an arbitrary node and repeatedly adding the cheapest edge connecting the built tree to the rest. We use arrays to track min edge to tree.

{code in C language}

#include <stdio.h>
#include <limits.h>
#define MAXV 20
#define INF 1000000000

int graph[MAXV][MAXV];

int min_key(int key[], int inMST[], int n){
    int min = INF, min_index = -1;
    for(int v=0; v<n; v++){
        if(!inMST[v] && key[v] < min){
            min = key[v]; min_index = v;
        }
    }
    return min_index;
}

void prim(int n){
    int parent[MAXV];
    int key[MAXV];
    int inMST[MAXV];
    for(int i=0;i<n;i++){ key[i]=INF; inMST[i]=0; parent[i]=-1; }
    key[0]=0; // start from vertex 0
    for(int count=0; count<n-1; count++){
        int u = min_key(key, inMST, n);
        if(u == -1) break;
        inMST[u] = 1;
        for(int v=0; v<n; v++){
            if(graph[u][v] && !inMST[v] && graph[u][v] < key[v]){
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    int total = 0;
    printf("Edges in MST:\n");
    for(int i=1;i<n;i++){
        if(parent[i] != -1){
            printf("%d - %d (w=%d)\n", parent[i], i, graph[parent[i]][i]);
            total += graph[parent[i]][i];
        }
    }
    printf("Total weight = %d\n", total);
}

int main(){
    int n = 5;
    int i,j;
    for(i=0;i<n;i++) for(j=0;j<n;j++) graph[i][j]=0;
    // example graph (undirected)
    graph[0][1]=2; graph[1][0]=2;
    graph[0][3]=6; graph[3][0]=6;
    graph[1][2]=3; graph[2][1]=3;
    graph[1][3]=8; graph[3][1]=8;
    graph[1][4]=5; graph[4][1]=5;
    graph[2][4]=7; graph[4][2]=7;
    graph[3][4]=9; graph[4][3]=9;
    prim(n);
    return 0;
}

{their time and space complexity}

• Time: O(n^2) with simple array implementation. With a priority queue, O(m log n).

• Space: O(n^2) for matrix.

{output and dry run of the output}
Sample output:

Edges in MST:
0 - 1 (w=2)
1 - 2 (w=3)
1 - 4 (w=5)
0 - 3 (w=6)
Total weight = 16

Dry run: start at 0 -> add cheapest connecting vertex each step (1 first, then 2 via 1, etc.)

16) Floyd’s Algorithm (Floyd–Warshall)

{short text rich description}
Floyd–Warshall computes shortest paths between all pairs of vertices in a weighted graph (handles positive/negative weights but no negative cycles). Uses dynamic programming over triple loops.

{code in C language}

#include <stdio.h>
#define MAXV 20
#define INF 1000000000

int dist[MAXV][MAXV];

void floyd(int n){
    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] < INF && dist[k][j] < INF){
                    int nd = dist[i][k] + dist[k][j];
                    if(nd < dist[i][j]) dist[i][j] = nd;
                }
            }
        }
    }
}

int main(){
    int n = 4;
    int i,j;
    for(i=0;i<n;i++) for(j=0;j<n;j++) dist[i][j] = (i==j)?0:INF;
    // edges
    dist[0][1] = 5;
    dist[0][3] = 10;
    dist[1][2] = 3;
    dist[2][3] = 1;
    floyd(n);
    printf("All-pairs shortest distances:\n");
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(dist[i][j] >= INF) printf("INF ");
            else printf("%d ", dist[i][j]);
        }
        printf("\n");
    }
    return 0;
}

{their time and space complexity}

• Time: O(n^3).

• Space: O(n^2).

{output and dry run of the output}
Sample output:

All-pairs shortest distances:
0 5 8 9 
INF 0 3 4 
INF INF 0 1 
INF INF INF 0 

Dry run: Using intermediate nodes k=0..3, update distances. For example, dist[0][2] initially INF becomes dist[0][1]+dist[1][2]=5+3=8, then maybe improved via other k.