Minimum Spanning Tree

Dijkstra's Algorithm

int array[10] = {1,2,3,4,5,6,7,8,9,10};
int map[10][10];
int visit[10];
int parent[10];
int distance[10];
 
void Minimum_Spanning_Tree()
{
    int i, j, k, min, min_value;
 
    for (i = 0; i < 10; i++) {
        distance[i] = 0x7fffffff;
    }
 
    parent[0] = 0;            // arbitrarily select one node -> select 0
    distance[0] = 0;
 
    for (i = 0; i < 10; i++) {
 
        min_value = 0x7fffffff;
        min = -1;
 
        for (j = 0; j < 10; j++)
            if (!visit[i] && distance[j] < min_value) {
                min_value = distance[j];
                min = j;
            }
 
        if (min == -1)
            return;
        visit[min] = 1;
 
        for (k = 0; k < 10; k++) {
            if (!visit[k] && map[min][k] && map[min][k] < distance[k]) {   // a little different with SP
                distance[k] = map[min][k];
                parent[k] = min;
            }
        }
    }
}

Time Complexity

Same for adjacency matrix and adjacency list

Best:
O(n) — non of the nodes are connected to each other

Avg:
O(n2)?

Worst:
O(n2) — all nodes are connected to each other

n times {                            // for strong connected graph, we should do n times
    n times searching
                +
    n times scanning for adjacency matrix | e times scanning for adjacency list
}

Floyd's Algorithm

#define MIN(a, b) ((a) < (b))?(a):(b)
int D[10][10];               // D is used to store D_k[i][j]
int W[10][10];              // W is adjacent matrix
 
void Floyd()
{
    int i, j, k;
    for (i = 0; i < 10; i++)
        for (j = 0; j < 10; j++)
            D[i][j] = W[i][j];             // D = D0
 
    for (k = 0; k < 10; k++)
        for (i = 0; i < 10; i++)
            for (j = 0; j < 10; j++)
                D[i][j] = MIN(D[i][j], D[i][k] + D[k][j]);
}

Note:
Dk[i, j] =
min(Dk-1[i, j], Dk-1[i, k] + Dk-1[k, j])
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License