Dikjstra's Algorithm (Adjacency Matrix)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_NODES = 510;
int node_count, edge_count;
int graph[MAX_NODES][MAX_NODES];
int min_distance[MAX_NODES];
bool visited[MAX_NODES];

int dijkstra_shortest_path() {
    memset(min_distance, 0x3f, sizeof min_distance);
    min_distance[1] = 0;
    
    for (int iteration = 0; iteration < node_count; iteration++) {
        int current_node = -1;
        for (int node = 1; node <= node_count; node++) {
            if (!visited[node] && (current_node == -1 || min_distance[node] < min_distance[current_node])) {
                current_node = node;
            }
        }
        visited[current_node] = true;
        
        for (int neighbor = 1; neighbor <= node_count; neighbor++) {
            min_distance[neighbor] = min(min_distance[neighbor], min_distance[current_node] + graph[current_node][neighbor]);
        }
    }
    
    return min_distance[node_count] == 0x3f3f3f3f ? -1 : min_distance[node_count];
}

int main() {
    cin >> node_count >> edge_count;
    memset(graph, 0x3f, sizeof graph);
    
    for (int i = 0; i < edge_count; i++) {
        int from, to, weight;
        scanf("%d%d%d", &from, &to, &weight);
        graph[from][to] = min(graph[from][to], weight);
    }
    
    cout << dijkstra_shortest_path() << endl;
    return 0;
}

Floyd-Warshall Algorithm for All-Pairs Shortest Path

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_SIZE = 210;
int node_count, edge_count, query_count;
int distance_matrix[MAX_SIZE][MAX_SIZE];

void compute_all_pairs_shortest_path() {
    for (int intermediate = 1; intermediate <= node_count; intermediate++) {
        for (int start = 1; start <= node_count; start++) {
            for (int end = 1; end <= node_count; end++) {
                distance_matrix[start][end] = min(distance_matrix[start][end], 
                                                distance_matrix[start][intermediate] + distance_matrix[intermediate][end]);
            }
        }
    }
}

int main() {
    cin >> node_count >> edge_count >> query_count;
    
    for (int i = 1; i <= node_count; i++) {
        for (int j = 1; j <= node_count; j++) {
            distance_matrix[i][j] = (i == j) ? 0 : 0x3f3f3f3f;
        }
    }
    
    while (edge_count--) {
        int a, b, weight;
        cin >> a >> b >> weight;
        distance_matrix[a][b] = min(distance_matrix[a][b], weight);
    }
    
    compute_all_pairs_shortest_path();
    
    while (query_count--) {
        int x, y;
        cin >> x >> y;
        if (distance_matrix[x][y] > 0x3f3f3f3f / 2) {
            cout << "impossible" << endl;
        } else {
            cout << distance_matrix[x][y] << endl;
        }
    }
    return 0;
}

Prim's Algorithm for Minimum Spanning Tree

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_NODES = 510;
int adjacency_matrix[MAX_NODES][MAX_NODES];
bool in_mst[MAX_NODES];
int distance_to_set[MAX_NODES];
int total_nodes, total_edges;
int total_weight = 0;

int prim_mst() {
    memset(distance_to_set, 0x3f, sizeof distance_to_set);
    
    for (int iter = 0; iter < total_nodes; iter++) {
        int selected_node = -1;
        for (int node = 1; node <= total_nodes; node++) {
            if (!in_mst[node] && (selected_node == -1 || distance_to_set[node] < distance_to_set[selected_node])) {
                selected_node = node;
            }
        }
        
        if (iter > 0 && distance_to_set[selected_node] == 0x3f3f3f3f) {
            return 0x3f3f3f3f;
        }
        
        if (iter > 0) {
            total_weight += distance_to_set[selected_node];
        }
        in_mst[selected_node] = true;
        
        for (int neighbor = 1; neighbor <= total_nodes; neighbor++) {
            distance_to_set[neighbor] = min(distance_to_set[neighbor], adjacency_matrix[selected_node][neighbor]);
        }
    }
    return total_weight;
}

int main() {
    cin >> total_nodes >> total_edges;
    memset(adjacency_matrix, 0x3f, sizeof adjacency_matrix);
    
    while (total_edges--) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u != v) {
            adjacency_matrix[u][v] = adjacency_matrix[v][u] = min(adjacency_matrix[u][v], w);
        }
    }
    
    int result = prim_mst();
    if (result == 0x3f3f3f3f) {
        cout << "impossible" << endl;
    } else {
        cout << result << endl;
    }
    return 0;
}

Kruskal's Algorithm with Union-Find

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_EDGES = 200010;
int parent[MAX_EDGES];
int node_count, edge_count;

struct Edge {
    int source, destination, weight;
};

Edge edges[MAX_EDGES];
int total_weight = 0, edges_used = 0;

bool compare_edges(Edge a, Edge b) {
    return a.weight < b.weight;
}

int find_parent(int node) {
    if (parent[node] != node) {
        parent[node] = find_parent(parent[node]);
    }
    return parent[node];
}

int main() {
    cin >> node_count >> edge_count;
    for (int i = 1; i <= node_count; i++) {
        parent[i] = i;
    }
    
    for (int i = 1; i <= edge_count; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {u, v, w};
    }
    
    sort(edges + 1, edges + edge_count + 1, compare_edges);
    
    for (int i = 1; i <= edge_count; i++) {
        int u_root = find_parent(edges[i].source);
        int v_root = find_parent(edges[i].destination);
        
        if (u_root != v_root) {
            total_weight += edges[i].weight;
            edges_used++;
            parent[u_root] = v_root;
        }
    }
    
    if (edges_used < node_count - 1) {
        cout << "impossible" << endl;
    } else {
        cout << total_weight << endl;
    }
    return 0;
}