5 - UCS

#include <stdio.h>
#include <vector>
#include <algorithm>

#define MAX 1000

struct Node{
    int n, weight;
}node; //struct untuk deklarasi type 'node' sehingga dapat memiliki attribut suatu titik

int flag[MAX], previ[MAX], dist[MAX], vertex, source, destination;
int graph[MAX][MAX];

std::vector <Node> vec_nodes;

void add(int N, int cost){
    node.n = N;
    node.weight = cost;
    vec_nodes.push_back(node);
}

bool data_sort(Node a, Node b){
    return a.weight < b.weight;
}

void UCS(){
    for(int i = 1; i <= vertex; i++){ //Initiate value tiap penyimpanan
        flag[i] = 0;
        dist[i] = 10e9;
        previ[i] = -1;
    }
    dist[source] = 0; //Value untuk source node (35 - 38)
    previ[source] = -1;
    add(source, 0);

    while(!vec_nodes.empty()){
        int u = vec_nodes[0].n;
        vec_nodes.erase(vec_nodes.begin());
        for(int i = 1; i <= vertex; i++){
            if(graph[u][i] != 0 && flag[i] == 0){ //Node u dan i terhubung langsung oleh 1 garis
                if(dist[u] + graph[u][i] < dist[i]){ //Kondisi untuk jika jaraknya lebih kecil maka kemungkinan akan menjadi hasil final
                    dist[i] = dist[u] + graph[u][i];
                    previ[i] = u;
                }
                add(i, dist[i]); //Add node i ke vector yang menyimpan jaraknya
                sort(vec_nodes.begin(), vec_nodes.end(), data_sort); //Vector diurutkan sesuai prinsip UCS yang mengambil node dengan jarak terpendek dari root
            }
        }
        flag[u] = -1; //Tanda bahwa titik tsb sudah ditemukan
    }
}

void printPath(int destination){
    if(destination == source)
        printf("%d ", source);
    else if(previ[destination] == -1)
        return;
    else{
        printPath(previ[destination]);
        printf("%d ", destination);
    }
}

void printDistance(){
    int i;
    printf("\nDistance Measurement:\n");
    for(i = 1; i <= vertex; ++i){
        printf("%d -> %d = %d \n", source, i, dist[i]);
    }
    printf("\n");
}

int main(){
    int edges, u, v, w;
    printf("Enter number of edges: "); //Jumlah garis
    scanf("%d", &edges);
    vertex = -1;
    printf("Enter %d edges (from-to-distance) each separated by a space:\n", edges);
    for(int i = 0; i < edges; i++){ //Buat input data graf
        scanf("%d %d %d", &u, &v, &w);
        graph[u][v] = w;
        vertex = std::max(u, std::max(v, vertex)); //Buat nyari jumlah vertex
    }
    printf("Enter source and destination: ");
    scanf("%d %d", &source, &destination);
    UCS(); //Algoritma utama Uniform-cost search
    printDistance(); //Jarak terpendek source node ke semua titik

    printf("The path from %d to %d is given below : \n", source, destination);
    printPath(destination); //Untuk print jalur source node ke target node

    return 0;
}