1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

template <class Type>
void Dijkstra(int n, int v, Type dist[], int prev[], Type **c)
{
    bool s[maxint];             // Determine whether the shortest path has been found
    for (int i = 1; i <= n; i++)
    {
        dist[i] = c[v][i];
        s[i] = false;
        if (dist[i] == maxint)
        {
            prev[i] = 0;
        }
        else
        {
            prev[i] = v;
        }
    }
    dist[v] = 0;
    s[v] = true;
    for (int i = 1; i < n; i++)
    {
        Type temp = maxint;
        int u = v;
        for (int j = 1; j <= n; j++)
        {
            if ((!s[j]) && (dist[j] < temp))
            {
                u = j;
                temp = dist[j];
            }
        }
        s[u] = true;
        for (int j = 1; j <= n; j++)
        {
            if ((!s[j]) && (c[u][j] < maxint))
            {
                Type newdist = dist[u] + c[u][j];
                if (newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
        }
    }
}

The overall time required to complete the algorithm above is \(O(n^2)\).

For the directed graph given in problem description 2.1.1 above, we compute the shortest paths from source vertex 1 to other vertices and trace its iteration process, recorded in the table below:

For a detailed step-by-step analysis of the algorithm above, refer to this article: Dijkstra's Shortest Path Algorithm - A Visual Introduction

2.2 Minimum Spanning Tree

2.2.1 Problem Description

Let \(G(V,E)\) be an undirected connected weighted graph. The weight of each edge \((v,w)\) in \(E\) is \(c[v][w]\). If a subgraph \(G'\) of \(G\) is a tree containing all vertices of \(G\), then \(G'\) is called a spanning tree of \(G\). Among these, the spanning tree with the minimum total cost (or the minimum total edge weight) is called the Minimum Spanning Tree.

Before solving this problem, we need to understand its properties. Let \(G=(V,E)\) be a connected weighted graph, and let \(U\) be a proper subset of \(V\). If \((u,v)\in E\), \(u\in U\), \(v \in V-U\), and \((u,v)\) has the minimum weight among all such edges crossing the cut, then this edge must belong to a minimum spanning tree of \(G\).

2.2.2 Prim's Algorithm

For the aforementioned \(G\), first set \(S=\left\{1\right\}\). As long as \(S\) is a proper subset of \(V\), make the following choice: pick the edge \((i,j)\) with minimum \(c[i][j]\) satisfying \(i \in S\) and \(j \in V-S\), and add vertex \(j\) to \(S\). Repeat until \(S=V\). In simple terms, it involves iteratively adding the "shortest" connecting edge to the spanning tree until all vertices are included, thereby obtaining the minimum spanning tree. Take the following connected weighted graph as an example:

The image below illustrates the process of Prim's algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

template <class Type>
void Prim(int n, Type** c)
{
    Type lowcost[maxint];
    int closest[maxint];
    bool s[maxint];
    s[1] = true;
    for (int i = 2; i <= n; i++)
    {
        lowcost[i] = c[1][i];
        closest[i] = 1;
        s[i] = false;
    }

    for(int i = 1; i < n; i++)
    {
        Type min = inf;
        int j = 1;
        for(int k = 2; k <= n; k++)
        {
            if((lowcost[k] < min) && (!s[k]))
            {
                min = lowcost[k];
                j = k;
            }
        }
    }

    cout << "(" << closest[j] << "," << j << ")" << endl;
    s[j] = ture;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

template <class Type>

class EdgeNode
{
    freind ostream& operator<< (ostream&,EdgeNode<Type>);
    friend bool Kruskal(int, int, EdgeNode<Type>*, EdgeNode<Type>* );
    friend void main(void);
public:
    operator Type() const
    {
        return weight;
    }
private:
    Type weight;
    int u, v;
}

//Kruskal algorithm
template <class Type>
bool Kruskal(int n, int e, EdgeNode<Type> E[], EdgeNode<Type> t[])
{
    MinHeap<EdgeNode<Type>> H(1); // Use a min-heap to store sorted edges
    H.Initialize(E, e, e);
    UnionFind UF(n); // This is an abstract disjoint-set data structure supporting union and find operations
    int k = 0;
    while (e && k < n-1)
    {
        EdgeNode<int> x;
        H.DeleteMin(x);
        e--;
        int a = U.Find(x.u);// Find operation, returns the representative/root of the component containing the vertex
        int b = U.Find(x.v);
        if (a != b)// Check if vertices are in the same component
        {
            t[k++] = x;
            U.Union(a, b);// Union operation, merges the two components
        }
        H.Deactivate(x);
        return (k == n-1);
    }
}