Solusi brute force

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

// Fungsi untuk mencari rute terpendek antara dua titik dalam graf berbobot dengan pendekatan brute force
void bruteForceShortestPath(vector<vector<int>>& graph, int source, int destination, int current, int cost, int& minCost) {
    int n = graph.size(); // Jumlah titik dalam graf

    // Basis: Jika titik saat ini adalah tujuan, perbarui jarak terpendek jika lebih kecil
    if (current == destination) {
        minCost = min(minCost, cost);
        return;
    }

    // Rekursi: Coba semua kemungkinan rute dari titik saat ini
    for (int i = 0; i < n; i++) {
        // Cek apakah ada sisi yang menghubungkan titik saat ini dengan titik i
        if (graph[current][i] != 0) {
            // Lanjutkan ke titik i jika belum dikunjungi
            if (i != source) {
                bruteForceShortestPath(graph, source, destination, i, cost + graph[current][i], minCost);
            }
        }
    }
}

int main() {
    // Contoh penggunaan
    int n = 5; // Jumlah titik dalam graf
    vector<vector<int>> graph = {
        {0, 2, 0, 1, 0},
        {2, 0, 4, 0, 5},
        {0, 4, 0, 3, 0},
        {1, 0, 3, 0, 6},
        {0, 5, 0, 6, 0}
    };

    int source = 0; // Titik awal
    int destination = 4; // Titik tujuan

    int minCost = INF; // Inisialisasi jarak terpendek dengan nilai maksimum
    bruteForceShortestPath(graph, source, destination, source, 0, minCost);

    // Cetak jarak terpendek dari titik awal ke titik tujuan
    cout << "Jarak terpendek dari titik " << source << " ke titik " << destination << " adalah: " << minCost << endl;

    return 0;
}