# Dijkstra's Algorithm

## Thuật toán Dijkstra
Dijkstra's Algorithm là thuật toán tìm đường đi có chi phí nhỏ nhất từ một đỉnh đến tất cả các đỉnh còn lại trong đồ thị có trọng số (trọng số không âm).

Thuật toán Dijkstra bình thường sẽ có độ phức tạp là O(V^2). Tuy nhiên ta có thể sử dụng kết hợp các cấu trúc dữ liệu khác để giảm độ phức tạp:
* Dùng Heap (priority queue) có độ phức tạp: O(ELogV).
* Dùng kết hợp cấu trúc dữ liệu cây nhị phân tìm kiếm độ phức tạp là: O(ElogV).

## Mô phỏng cách chạy thuật toán

## Ý tưởng của thuật toán

# C++
## Khai báo thư viện và các biến toàn cục

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 100
const int INF = 1e9;
vector<vector<pair<int, int>>> graph;
vector<int> dist(MAX, INF);
int path[MAX];

struct option
{
    bool operator() (const pair<int, int> &a, const pair<int, int> &b) const
    {
        return a.second > b.second;
    }
};

### Source Code Dijkstra

void Dijkstra(int s)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, option> pq;
    pq.push(make_pair(s, 0));
    dist[s] = 0;

    while (!pq.empty())
    {
        pair<int, int> top = pq.top();
        pq.pop();
        int u = top.first;
        int w = top.second;

        for (int i = 0; i < graph[u].size(); i++) {
            pair<int, int> neighbour = graph[u][i];
            if (w + neighbour.second < dist[neighbour.first]) {
                dist[neighbour.first] = w + neighbour.second;
                pq.push(pair<int, int>(neighbour.first, dist[neighbour.first]));
                path[neighbour.first] = u;
            }
        }
    }
}

### Hàm Main

int main() {
    int n, s, t;
    cin >> n;
    s = 0, t = 4;
    graph = vector<vector<pair<int, int>>> (MAX + 5, vector<pair<int, int>>());
    int d = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> d;
            if (d > 0)
                graph[i].push_back(pair<int, int>(j, d));
        }
    }

    Dijkstra(s);
    int ans = dist[t];
    cout << ans;

    return 0;
}

# Python
Khai báo class Node với id là tên đỉnh, dist là chi phí. Define operator ```__lt__``` (less than) cho class, so sánh theo dist nhỏ hơn, dùng trong Priority Queue.

### Khai báo class Node

import queue
MAX = 100
INF = int(1e9)

class Node:
    def __init__(self, id, dist):
        self.dist = dist
        self.id = id

    def __lt__(self, other):
        return self.dist <= other.dist

### Source Code Dijkstra

def Dijkstra(s):
    pq = queue.PriorityQueue()
    pq.put(Node(s, 0))
    dist[s] = 0

    while pq.empty() == False:
        top = pq.get()
        u = top.id
        w = top.dist

        for neighbour in graph[u]:
            if w + neighbour.dist < dist[neighbour.id]:
                dist[neighbour.id] = w + neighbour.dist
                pq.put(Node(neighbour.id, dist[neighbour.id]))
                path[neighbour.id] = u

### Hàm Main

if __name__ == "__main__":
    n = int(input())
    s, t = 0, 4
    graph = [[] for i in range(n + 5)]
    dist = [INF for i in range(n + 5)]
    path = [-1 for i in range(n + 5)]

    for i in range(n):
        d = list(map(int, input().split()))
        for j in range(n):
            if d[j] > 0:
                graph[i].append(Node(i, d[j]))

    Dijkstra(s)
    ans = dist[t]
    print(ans)