Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Đường đi ngắn nhất đơn nguồn, trọng số không âm (Dijkstra)


Thuật toán đường đi ngắn nhất đơn nguồn (trọng số không âm) gọi là Dijkstra. Cho đồ thị G(V,E) với ma trận kề và đỉnh nguồn. Dijkstra tìm đường đi ngắn nhất từ nguồn đến mọi đỉnh khác.

Đường đi ngắn nhất đơn nguồn, trọng số không âm (Dijkstra)

Từ nút bắt đầu đến bất kỳ nút nào, tìm khoảng cách nhỏ nhất. Đồ thị biểu diễn bằng ma trận kề (ma trận chi phí tương tự).

Đầu vào − Ma trận kề:

0 3 6 ∞ ∞ ∞ ∞
3 0 2 1 ∞ ∞ ∞
6 2 0 1 4 2 ∞
∞ 1 1 0 2 ∞ 4
∞ ∞ 4 2 0 2 1
∞ ∞ 2 ∞ 2 0 1
∞ ∞ ∞ 4 1 1 0

Đầu ra −

0 to 1, Using: 0, Cost: 3
0 to 2, Using: 1, Cost: 5
0 to 3, Using: 1, Cost: 4
0 to 4, Using: 3, Cost: 6
0 to 5, Using: 2, Cost: 7
0 to 6, Using: 4, Cost: 7

Thuật toán

dijkstraShortestPath(n, dist, next, start)

Đầu vào − Tổng số nút n, danh sách khoảng cách, danh sách next, đỉnh bắt đầu.

Đầu ra − Các đường đi ngắn nhất từ start đến mọi đỉnh khác.

Begin
    tạo danh sách status lưu trạng thái nút được chọn
    for all vertices u in V do
        status[u] := unconsidered
        dist[u] := khoảng cách từ nguồn dùng ma trận chi phí
        next[u] := start
    done
    status[start] := considered, dist[start] := 0, next[start] := φ
    while lấy đỉnh unconsidered u có khoảng cách nhỏ nhất do
        status[u] := considered
        for all vertex v in V do
            if status[v] = unconsidered then
                if dist[v] > dist[u] + cost[u,v] then
                    dist[v] := dist[u] + cost[u,v]
                    next[v] := u
                done
            done
        done
End

Ví dụ (C++)

#include 
#define V 7
#define INF 999
using namespace std;
int costMat[V][V] = { ... };
int minimum(int *status, int *dis, int n){ ... }
void dijkstra(int n, int *dist, int *next, int s){ ... }
main(){ ... }

Đầu ra

0 to 1, Using: 0, Cost: 3
0 to 2, Using: 1, Cost: 5
0 to 3, Using: 1, Cost: 4
0 to 4, Using: 3, Cost: 6
0 to 5, Using: 2, Cost: 7
0 to 6, Using: 4, Cost: 7