Solusi Shortest Path

#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
void shortestPath(vector<vector<int>>& graph, int source, int destination) {
    int n = graph.size(); // Jumlah titik dalam graf
    vector<int> distance(n, INF); // Tabel jarak terpendek sementara
    vector<int> parent(n, -1); // Tabel parent untuk melacak rute

    distance[source] = 0; // Jarak dari titik awal ke dirinya sendiri adalah 0

    // Pemrograman dinamis
    for (int i = 0; i < n - 1; i++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                // Periksa apakah ada sisi yang menghubungkan titik u dan v
                if (graph[u][v] != 0) {
                    // Perbarui jarak terpendek jika ditemukan jarak yang lebih kecil
                    if (distance[u] != INF && distance[u] + graph[u][v] < distance[v]) {
                        distance[v] = distance[u] + graph[u][v];
                        parent[v] = u;
                    }
                }
            }
        }
    }

    // Cetak rute terpendek dari titik awal ke titik tujuan
    cout << "Rute terpendek dari titik " << source << " ke titik " << destination << " adalah: ";
    int current = destination;
    cout << current;
    while (parent[current] != -1) {
        cout << " <- " << parent[current];
        current = parent[current];
    }
    cout << endl;

    // Cetak jarak terpendek dari titik awal ke titik tujuan
    cout << "Jarak terpendek dari titik " << source << " ke titik " << destination << " adalah: " << distance[destination] << endl;
}

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

    shortestPath(graph, source, destination);

    return 0;
}