datstruct final

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define SIZE 100
#define INFINITY 99999
#define NOT_DEFINED 0

int readFile(char *);
int djikstra();
void CLR();

int graph[SIZE][SIZE];
int graph_dimension;
char cities[SIZE][SIZE];

int from;
int dest;

int main(int argc, char **argv)
{
    readFile("kota.txt");

    int ch;
    do
    {
    	CLR();
    	printf("Welcome to Map Application\n\n");
    	printf("Menus :\n");
		printf("1. Cities list\n");
        printf("2. Set start and finish\n");
        printf("3. Exit program\n\n\n");

        do
        {
            printf("> Please select your choice : ");
            scanf("%d", &ch);
        } while (ch < 1 || ch > 3);
        switch (ch)
        {
        case 1:
        {
            CLR();
            printf("Available cities :\n\n");
            for (int i = 0; i < sizeof(cities) && i < graph_dimension; i++)
            {
                printf("%d. %s\n", i + 1, cities[i]);
            }
            printf("\n");
            getch();
            break;
        }
        case 2:
        {
            CLR();
            printf("Available cities :\n\n");
            for (int i = 0; i < sizeof(cities) && i < graph_dimension; i++)
            {
                printf("[ %d ] %s\n", i + 1, cities[i]);
            }
            printf("\n");
            printf("Insert start : ");
            scanf("%d", &from);
            printf("Insert finish : ");
            scanf("%d", &dest);
            from -= 1;
            dest -= 1;

            djikstra();
            getch();
            break;
        }
        }
    } while (ch != 3);

    printf("\n\n");
    return 0;
}

void CLR()
{
    system("@cls||clear");
}

int isHeapEmpty(int heap[SIZE])
{
    int i, res = 0;
    for (i = 0; i < SIZE && i < graph_dimension; i++)
    {
        if (heap[i] == 1)
        {
            res = 1;
            break;
        }
    }
    return res;
}

int extractMin(int heap[SIZE], int dist[SIZE], int current)
{
    int i, min = INFINITY, res = -1;
    for (i = 0; i < SIZE && i < graph_dimension; i++)
    {
        if (min > dist[i] && heap[i] != 0)
        {
            min = dist[i];
            res = i;
        }
    }
    return res;
}

int djikstra()
{
    int i, j, start, near, current;
    int dist[SIZE], heap[SIZE], parent[SIZE];

    start = current = start;
    for (i = 0; i < SIZE && i < graph_dimension; i++)
    {
        dist[i] = INFINITY;
        heap[i] = 1;
        parent[i] = NOT_DEFINED;
    }
    dist[0] = 0;

    while (isHeapEmpty(heap) == 1)
    {
        near = extractMin(heap, dist, current);
        if (near < 0)
            break;
        heap[near] = 0;
        for (i = 0; i < SIZE && i < graph_dimension; i++)
        {
            if (heap[i] == 1 && (dist[i] > dist[near] + graph[near][i]))
            {
                dist[i] = dist[near] + graph[near][i];
                parent[i] = near;
            }
        }
        current = near;
    }

    for (i = 0; i < SIZE && i < graph_dimension; i++)
    {
        if (i == start)
            continue;
        current = i;
        if (i == dest)
        {
            if (dist[i] >= INFINITY)
            {
                printf("\n\n (S%d,S%d): Couldn't find path'!\n", start, i);
                continue;
            }
            printf("\nTotal distance from city %s to city %s : %d km\nTotal cost : Rp %d", cities[start], cities[i], dist[i], dist[i]*1500);
            printf("\n");
        }
    }
    return 0;
}

int readFile(char *filename)
{
    FILE *stream = fopen(filename, "r");

    char line[1024];
    int maxi;
    int maxj;

    int i = 0;
    while (fgets(line, 1024, stream))
    {
        char *tmp = strdup(line);

        const char *tok;
        int j;
        for (tok = strtok(line, ",");
             tok && *tok;
             tok = strtok(NULL, ",\n"))
        {
            if (j == 0)
            {
                strcpy(cities[i], tok);
            }
            else
            {
                int weight = atoi(tok);
                if (weight == NOT_DEFINED)
                {
                    graph[i][j - 1] = INFINITY;
                }
                else
                {
                    graph[i][j - 1] = weight;
                }
            }
            j++;
        }
        free(tmp);
        graph_dimension = j - 1;
        j = 0;
        i++;
    }

    fclose(stream);
    return 0;
}