short_path

#include <stdio.h>
#define MAX_VERICES    3
int cost[][MAX_VERICES] = {
    {0, 4, 11},
    {6, 0, 2},
    {3, 32767, 0}
};

int distance[MAX_VERICES];
short int found[MAX_VERICES];
int n = MAX_VERICES;

void shortestpath(int, int [][MAX_VERICES], int [], int, short []);
int choose(int [], int , short []);

void main(void)
{
    
}

void shortestpath(int v, int cost[][MAX_VERICES], int distance[], int n, short found[])
{
    int i, u, w;
    for(i=0; i<n; ++i)
    {
        found[i] = false;
        distance[i] = cost[v][i];
    }
    found[v] = true;
    distance[v] = 0;
    
    for(i=0; i<n-2; ++i)
    {
        u = choose(distance, n, found);
        found[u] = true;
        for(w=0; w<n; ++w)
            if(!found[w])
                if(distance[u] + cost[u][w] < distance[w])
                    distance[w] = distance[u] + cost[u][w];
    }
}

int choose(int distance[], int n, short found[])
{
    // 조사 안된 정점 중에서 distance 값이 최소 인 것을 찾음
    int i, min, minpos;
    min = 32767;
    minpos = -1;

    for(i=0; i<n; ++i)
    {
        if(distance[i] < min && !found[i])
        {
            min = distance[i];
            minpos = i;
        }
    }

    return minpos;
}