dijkstra.c

#include <stdlib.h>
#include <stdio.h>

#define STATION_NUMBER (6)
#define START_STATION  (0)

char* stations[] = { "横浜", "武蔵小杉", "品川", "渋谷", "新橋", "溜池山王" };

int current_cost[STATION_NUMBER];
int fix[STATION_NUMBER];

int adjacency_matrix[STATION_NUMBER][STATION_NUMBER] = {
    {  0, 12, 28,  0,  0,  0 },
    { 12,  0, 10, 13,  0,  0 },
    { 28, 10,  0, 11,  7,  0 },
    {  0, 13, 11,  0,  0,  9 },
    {  0,  0,  7,  0,  0,  4 },
    {  0,  0,  0,  9,  4,  0 },
};

int main(void)
{
    int i, min_station, min_time, new_time;

    for(i = 0; i < STATION_NUMBER; i++) {
        current_cost[i] = -1;
        fix[i] = 0;
    }
    current_cost[0] = 0;

    for(;;) {
        min_time = -1;
        for(i = 0; i < STATION_NUMBER; i++) {
            if(fix[i] == 0 && current_cost[i] != -1) {
                if(min_time == -1 || min_time > current_cost[i]) {
                    min_time = current_cost[i];
                    min_station = i;
                }
            }
        }

        if(min_time == -1)
            break;
        
        for(i = 0; i < STATION_NUMBER; i++) {
            if(fix[i] == 0 && adjacency_matrix[min_station][i] > 0) {
                new_time = min_time + adjacency_matrix[min_station][i];
                if ( current_cost[i] == -1 || new_time < current_cost[i] ) {
                    current_cost[i] = new_time;
                }
            }
        }

        fix[min_station] = 1;
    }

    for(i = 0; i < STATION_NUMBER; i++) {
        printf("%sの最短所要時間は%d分\n", stations[i], current_cost[i]);
    }

    return EXIT_SUCCESS;
}