Djikstra

#include <stdio.h>
#include <stdlib.h>
#define M 100
#define N 5

typedef int itemType;
typedef struct {
    itemType data[N];
    int indeks;
} stack;

typedef struct {
    int count;
    int front;
    int rear;
    itemType data[N];
}queue;

void inisialisasiQueue(queue *);
int empty_q(queue *);
int full_q(queue *);
void enqueue(itemType, queue *);
itemType dequeue(queue *);

void inisialisasiStack(stack *);
int empty_s(stack *);
int full_s(stack *);
void push(itemType, stack *);
void push(itemType, stack *);
itemType pop(stack *);

void djikstra();
void inisialisasiTQ();
void inisialisasiR();
int ada(int, queue *);
void baca_rute();

int QQ[][6]=
    {{M,1,3,M,M,M},
    {M,M,1,M,5,7},
    {3,M,M, 2, M, M},
    {M,M,M,M,1,M},
    {M,4,M,M,M,2},
    {M,M,M,M,M,M}};

int Q[][5]=
    {{M, 1, 3, M, M},
     {M, M, 1, M, 5},
     {3, M, M, 2, M},
     {M, M, M, M, 1},
     {M, 4, M, M, M},
};
int TQ[N], R[N];

int asal, tuj;
int main()
{
    int i;

    puts("Graph DJIKSTRA");
    djikstra();
    baca_rute();
    printf("Matriks TQ : ");
    for(i=0; i<N; i++)
        printf("%d ", TQ[i]);
    puts("");
    printf("Matriks R : ");
    for(i=0; i<N; i++)
        printf("%d ", R[i]);
    puts("");
    return 0;
}

void baca_rute(){
    int tuj_asli;
    stack tumpukan;

    inisialisasiStack(&tumpukan);
    tuj_asli = tuj;
    printf("\nRute dari %d ke %d = ", asal+1, tuj+1);
    while(R[tuj] != -1) {
        push(R[tuj], &tumpukan);
        tuj = R[tuj];
    }
    //printf("%d - ", asal+1);
    while(!empty_s(&tumpukan)) {
        printf("%d - ", pop(&tumpukan)+1);
    }
    printf("%d\n", tuj_asli+1);

    printf("Total beban = %d\n", TQ[tuj_asli]);
}

void djikstra(){
    int i, cn;
    queue antrian;

    printf("Masukkan asal : ");
    scanf("%d", &asal);
    asal--;
    fflush(stdin);
    printf("Masukkan tujuan : ");
    scanf("%d", &tuj);
    tuj--;
    inisialisasiTQ();
    inisialisasiR();
    inisialisasiQueue(&antrian);
    enqueue(asal, &antrian);
    while(!empty_q(&antrian)){
        cn = dequeue(&antrian);
        i=0;
        while(i<N){
            if(Q[cn][i] != M){
                if(Q[cn][i] + TQ[cn] <TQ[i]){
                    TQ[i] = Q[cn] [i] + TQ[cn];
                    R[i] = cn;
                //  hsl = ada(i, &antrian);
                    if(i!=asal && i!=tuj && !ada(i, &antrian))
                        enqueue(i, &antrian);
                }

            }
            i++;
        }
    }
}

int ada(itemType x, queue *q){
    int hsl=0, i;

    for(i=0; i<N; i++){
        if(q->data[i] == x)
            hsl=1;
    }
    return hsl;
}

void inisialisasiR(){
    int i;

    for(i=0; i<N; i++){
        R[i] = -1;
    }
}

void inisialisasiTQ(){
    int i;

    for(i=0; i<N; i++){
        if(i==asal)
            TQ[i] = 0;
        else
            TQ[i] = M;
    }
}

void inisialisasiQueue(queue *q){
    q->count = 0;
    q->front = 0;
    q->rear = 0;
}

int empty_q(queue *q){
    if(q->count == 0)
        return 1;
    else
        return 0;
}

int full_q(queue *q){
    if(q->count == N)
        return 1;
    else
        return 0;
}

void enqueue(itemType x, queue *q) {
    if (full_q(q)) {
        puts("\nSTOP!!!");
        puts("Queue Penuh! Data terakhir Gak bs masuk!");
    }
    else {
        q->data[q->rear] = x;

        q->rear = (q->rear + 1) % N;
        ++(q->count);
    }
}

itemType dequeue(queue *q) {
    itemType tampung;

    if(empty_q(q)) {
        puts("\nTidak dapat mengambil data !");
        puts("Queueu Kosong!\n");
        tampung = ' ';
    }
    else {
        tampung = q->data[q->front];

        q->front = (q->front + 1) % N;
        --(q->count);
    }
    return tampung;   //data yang diambil dari posisi front
}




void inisialisasiStack(stack *s){
    s->indeks = 0;
}

int full_s (stack *s){
    if(s->indeks == N)
        return 1;
    else
        return 0;
}

int empty_s(stack *s){
    if(s->indeks == 0)
        return 1;
    else
        return 0;
}

void push(itemType x, stack *s){
//  if(full_q (queue *q))
//      puts("\nStack sudah penuh, data terakhir ga bs masuk!");
//  else{
        s->data[s->indeks] = x;
        ++s->indeks;
//  }
}

itemType pop(stack *s){
    itemType tampung;

    if(empty_s(s)) {
        puts("Stack kosong, gak bisa ngambil data apapun");
        tampung = ' ';
    }
    else {
        --s->indeks;
        tampung = s->data[s->indeks];
    }
    return tampung;
}