Shortest path & minimum spanning tree algorithm

[nguyenchiemminhvu (NCMV)]

Hồi sáng lên trường làm về 2 bài này, giờ tiện tay post code lên cho mấy bạn chưa học tham khảo.

[nguyenchiemminhvu (NCMV)]

Shortest path (Dijkstra): http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

#include <iostream>
#include <vector>
#include <cassert>
#include <limits.h>
#include <stack>
using namespace std;

#define Max_Ver 50
int graph[Max_Ver][Max_Ver];
int num_edge, num_ver;
int parent[Max_Ver],length[Max_Ver];
bool sptSet[Max_Ver];

void init() {

    cout << "Nhap so dinh: ";
    cin >> num_ver;
    cout << "Nhap so canh: ";
    cin >> num_edge;

    for(int i = 0; i <= num_ver; i++)   {

        parent[i] = i;
        sptSet[i] = false;
        length[i] = INT_MAX;
    }

    for(int i = 0; i < num_edge; i++)   {

        int src,dest,weight;
        cout << "Enter source, destination and weight: ";
        cin >> src >> dest >> weight;
        assert(src >= 1 && src <= num_ver && dest >= 1 && dest <= num_ver);

        graph[src][dest] = weight;
        graph[dest][src] = weight;
    }
}

void display_graph()    {

    cout << endl;
    for(int i = 1; i <= num_ver; i++)   {

        for(int j = 1; j <= num_ver; j++)   {

            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int find_min()  {

    int m = INT_MAX,m_index;
    for(int i = 1; i <= num_ver; i++)   {

        if(!sptSet[i] && m > length[i])
            m = length[i],m_index = i;
    }
    return m_index;
}

void shortestPath(int source = 1,int dest = num_ver) {

    int min_index;

    length[source] = 0;

    while(sptSet[dest] == false)    {

        min_index = find_min();

        sptSet[min_index] = true;

        for(int j = 1; j <= num_ver; j++)   {

            if(!sptSet[j] && graph[min_index][j] && length[min_index] + graph[min_index][j] < length[j])   {

                length[j] = length[min_index] + graph[min_index][j];
                parent[j] = min_index;
            }
        }
    }

    //output
    int temp = dest;
    stack<int> s;
    s.push(temp);
    while(parent[temp] != temp) {

        temp = parent[temp];
        s.push(temp);
    }

    cout << endl;
    cout << "Shortest Path length: " << length[dest] << endl;
    cout << "Path: ";
    while(!s.empty())   {

        cout << s.top();
        if(s.size() > 1)
            cout << " -> ";
        s.pop();
    }
}

int main()  {

    init();
    display_graph();
    shortestPath();
    return 0;
}

[nguyenchiemminhvu (NCMV)]

Minimum spanning tree (Prim): http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

#include <iostream>
#include <cassert>
#include <limits.h>
#include <vector>

using namespace std;

struct edge {

    int src;
    int dest;
    int weight;
};

#define Max_Ver 50
int graph[Max_Ver][Max_Ver];
int num_edge, num_ver;
bool mstSet[Max_Ver];

void init() {

    cout << "Nhap so dinh: ";
    cin >> num_ver;
    cout << "Nhap so canh: ";
    cin >> num_edge;

    for(int i = 0; i <= num_ver; i++)   {

        mstSet[i] = false;
    }

    for(int i = 0; i < num_edge; i++)   {

        int src,dest,weight;
        cout << "Enter source, destination and weight: ";
        cin >> src >> dest >> weight;
        assert(src >= 1 && src <= num_ver && dest >= 1 && dest <= num_ver);

        graph[src][dest] = weight;
        graph[dest][src] = weight;
    }
}

void display_graph()    {

    cout << endl;
    for(int i = 1; i <= num_ver; i++)   {

        for(int j = 1; j <= num_ver; j++)   {

            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

edge min_edge() {

    int m = INT_MAX;
    edge temp;
    for(int i = 1; i <= num_ver; i++)   {

        if(mstSet[i])   {

            for(int j = 1; j <= num_ver; j++)   {

                if(!mstSet[j] && graph[i][j] && m > graph[i][j])    {

                    m = graph[i][j];
                    temp.src = i,temp.dest = j,temp.weight = graph[i][j];
                }
            }
        }
    }

    return temp;
}

void min_spanning_tree(int source = 1)    {

    vector<edge> Set;
    mstSet[source] = true;

    while(Set.size() < num_ver - 1) {

        edge m = min_edge();
        mstSet[m.src] = true;
        mstSet[m.dest] = true;
        Set.push_back(m);
    }

    //output
    int length = 0;
    for(int i = 0; i < num_ver-1; i++)  {

        edge temp = Set.at(i);
        length += temp.weight;
        cout << "(" << temp.src << "," << temp.dest << ") = " << temp.weight << endl;
    }
    cout << "Length: " << length << endl;
}

int main()  {

    init();
    min_spanning_tree();

    return 0;
}

[nhatlonggunz]

1. Anh có thể nêu ngắn gọn ý tưởng không ạ?
2. Anh cho em hỏi, cái này có giống Depth-First vs Breadth-First Search (hình như VN gọi là loang) không?
3. Nếu khác thì cho em hỏi thuật toán này lợi gì hơn với DFS và BFS