# 14_Dijkstra

 

 

# The source code

#include <stdio.h>
#include <stdlib.h>
 
#define NUM_VERTEX 5
#define NUM_EDGES 8
struct node
{
    int v;
    int weight;
    struct node * next;
};
struct dijkstra
{
    int found; // K, 최단거리가 알려졌는가? 1:0
    int distance;
    int prev_vertex;
};
 
struct dijkstra dtable[NUM_VERTEX];
struct node * graph[NUM_VERTEX];
 
void addEdge(int v1, int v2, int w, int reverse)
{
    struct node *new_one = (struct node *)malloc(sizeof(struct node));
    struct node *cur = graph[v1];
 
    new_one->v = v2;
    new_one->next = 0;
    new_one->weight = w;
 
    if (cur == 0)
    {
        graph[v1] = new_one;
    }
    else
    {
        while (cur->next != 0)
        {
            cur = cur->next;
        }
        cur->next = new_one;
    }
 
    if (reverse == 1)
    {
        addEdge(v2, v1, w, 0);
    }
    return;
}
void initDtable()
{
    int i;
    for (i = 0; i < NUM_VERTEX; i++)
    {
        dtable[i].found = 0;
        dtable[i].distance = 99999;
        dtable[i].prev_vertex = -1;
    }
}
int findDijkstraNextVertex() //아직 found가 0이고 distance가 가장 짧은 vertex반환, return -1 : 모든 vertex의 최단거리를 찾은경우
{
    int i;
    int smallest_distance = 99999;
    int smallest_vertex = -1;
 
    for (i = 0; i < NUM_VERTEX; i++)
    {
        if (dtable[i].found == 0 && dtable[i].distance < smallest_distance)
        {
            smallest_vertex = i;
            smallest_distance = dtable[i].distance;
        }
    }
    return smallest_vertex;
}
void showDtable()
{
    for (int i = 0; i < NUM_VERTEX; i++)
    {
        printf("%d : %d(found) %d(distance) %d(previous vertex) \n", i, dtable[i].found, dtable[i].distance, dtable[i].prev_vertex);
    }
}
void updateDtable(int v)
{
    struct node *cur = graph[v];
    while (cur != 0)
    {
        //최단거리가 알려지지 않았고, 기존 알려진 거리보다 v를 통할 경우 더 가까우면 dtable update!
        if ((dtable[cur->v].found == 0) && (dtable[cur->v].distance > dtable[v].distance + cur->weight))
        {
            dtable[cur->v].distance = dtable[v].distance + cur->weight;
            dtable[cur->v].prev_vertex = v;
        }
        cur = cur->next;
    }
}
void doDijkstra(int v)
{
    int next_v = -1;
 
    dtable[v].distance = 0;
    while ((next_v = findDijkstraNextVertex()) != -1)
    {
        dtable[next_v].found = 1;
        updateDtable(next_v);
    }
 
    showDtable();
}
void main()
{
    addEdge(0, 1, 1, 1);
    addEdge(0, 2, 3, 1);
    addEdge(0, 4, 5, 1);
    addEdge(1, 2, 2, 1);
    addEdge(1, 4, 4, 1);
    addEdge(2, 4, 6, 1);
    addEdge(2, 3, 7, 1);
    addEdge(3, 4, 8, 1);
 
    initDtable();
    doDijkstra(0);
} 

 

# The result