| Lý thuyết đồ thị – Thuật toán Dijsktra

16 Aug Lý thuyết đồ thị – Thuật toán Dijsktra

Posted at 10:49h in Data Structures & Algorithms, General by admin 0 Comments

0 Likes

Cho một đồ thị G = (V, E) với:
– V là tập các đỉnh của đồ thị
– E là tập các cạnh của đồ thị sao cho trọng số các cung d(E) đều > 0.
– và một đỉnh cố định s nằm trong V.
Tìm đường ngắn nhất từ đỉnh s đến mỗi đỉnh v trong V.

Đồ thị trên có thể được biểu diễn bằng một ma trận 2 chiều m[r,c] sao cho mỗi giá trị m[r,c] là trọng số của cung nối đỉnh r và đỉnh c. Nếu không tồn tại cung nối giữa 2 đỉnh, giá trị này bằng 0. Bạn sẽ hiểu rõ hơn trong phần định nghĩa map của mã nguồn.

Thuật toán Dijkstra’s

1. Khởi tạo tập đỉnh Q = {}
2. Với mỗi đỉnh v trong V:
    dist[v] = infinity // tập chứa khoảng cách gần nhất tới mỗi đỉnh
    prev[v] = undefined // tập chứa đỉnh liền kề với một đỉnh, dùng để tìm đường
    đưa v vào Q
3. dist[s] = 0 // khoảng cách đến đỉnh xuất phát được set là 0
4. Lặp nếu Q chưa rỗng:
    tìm u sao cho dist[u] min
    gỡ u ra khỏi Q
    Lặp với mỗi v là đỉnh kề của u:
        alt = dist[u] + length(u, v) // tính khoảng cách đến v theo con đường đi qua u
	nếu alt < dist[v]: // nếu là khoảng cách ngắn hơn
	    dist[v] = alt // update khoảng cách mới
	    prev[v] = u // set đỉnh u là đỉnh kề của v
5. return dist[], prev[]

1. Khởi tạo tập đỉnh Q = {}

2. Với mỗi đỉnh v trong V:

dist[v] = infinity // tập chứa khoảng cách gần nhất tới mỗi đỉnh

prev[v] = undefined // tập chứa đỉnh liền kề với một đỉnh, dùng để tìm đường

đưa v vào Q

3. dist[s] = 0 // khoảng cách đến đỉnh xuất phát được set là 0

4. Lặp nếu Q chưa rỗng:

tìm u sao cho dist[u] min

gỡ u ra khỏi Q

Lặp với mỗi v là đỉnh kề của u:

alt = dist[u] + length(u, v) // tính khoảng cách đến v theo con đường đi qua u

nếu alt < dist[v]: // nếu là khoảng cách ngắn hơn

dist[v] = alt // update khoảng cách mới

prev[v] = u // set đỉnh u là đỉnh kề của v

5. return dist[], prev[]

Mã nguồn thuật toán:

class Program
    {
        static int[,] _map = new int[,] 
        { 
            { 0, 3, 0, 0, 0, 0, 0, 0},
            { 3, 0, 5, 2, 0, 0, 0, 0},
            { 0, 5, 0, 2, 1, 0, 0, 0},
            { 0, 2, 2, 0, 0, 3, 0, 0},
            { 0, 0, 1, 0, 0, 1, 4, 0},
            { 0, 0, 0, 3, 1, 0, 2, 0},
            { 0, 0, 0, 0, 4, 2, 0, 3},
            { 0, 0, 0, 0, 0, 0, 3, 0}
        };        

        static void Main(string[] args)
        {
            var numV = _map.GetLength(0);
            var dist = new int[numV];
            var prev = new int[numV];
            var d = ShortestPath(0, _map, ref dist, ref prev);

            Console.Read();
        }

        static int FindMinU(List<int> Q, int[] dist)
        {
            var minU = 1000000;
            var u = Q[0];
            for (int i = 0; i < Q.Count; i++)
            {
                if (minU > dist[Q[i]])
                {
                    minU = dist[Q[i]];
                    u = Q[i];
                }
            }

            return u;
        }

        static int[] ShortestPath(int source, int[,] map, ref int[] dist, ref int[] prev)
        {
            var Q = new List<int>();
            var numV = map.GetLength(0);

            for (int i = 0; i < map.GetLength(0); i++)
            {
                dist[i] = 1000000;
                prev[i] = -1;
                Q.Add(i);
            }

            dist[source] = 0;

            while (Q.Count() > 0)
            {
                var u = FindMinU(Q, dist);
                Q.Remove(u);

                for (int v = 0; v < numV; v++)
                {
                    if (map[u, v] > 0)
                    {
                        var alt = dist[u] + map[u, v];
                        if (alt < dist[v])
                        {
                            dist[v] = alt;
                            prev[v] = u;
                        }
                    }
                }
            }

            return dist;
        }
    }

class Program

{

static int[,] _map = new int[,]

{

{ 0, 3, 0, 0, 0, 0, 0, 0},

{ 3, 0, 5, 2, 0, 0, 0, 0},

{ 0, 5, 0, 2, 1, 0, 0, 0},

{ 0, 2, 2, 0, 0, 3, 0, 0},

{ 0, 0, 1, 0, 0, 1, 4, 0},

{ 0, 0, 0, 3, 1, 0, 2, 0},

{ 0, 0, 0, 0, 4, 2, 0, 3},

{ 0, 0, 0, 0, 0, 0, 3, 0}

};

static void Main(string[] args)

{

var numV = _map.GetLength(0);

var dist = new int[numV];

var prev = new int[numV];

var d = ShortestPath(0, _map, ref dist, ref prev);

Console.Read();

}

static int FindMinU(List<int> Q, int[] dist)

{

var minU = 1000000;

var u = Q[0];

for (int i = 0; i < Q.Count; i++)

{

if (minU > dist[Q[i]])

{

minU = dist[Q[i]];

u = Q[i];

}

return u;

}

static int[] ShortestPath(int source, int[,] map, ref int[] dist, ref int[] prev)

{

var Q = new List<int>();

var numV = map.GetLength(0);

for (int i = 0; i < map.GetLength(0); i++)

{

dist[i] = 1000000;

prev[i] = -1;

Q.Add(i);

}

dist[source] = 0;

while (Q.Count() > 0)

{

var u = FindMinU(Q, dist);

Q.Remove(u);

for (int v = 0; v < numV; v++)

{

if (map[u, v] > 0)

{

var alt = dist[u] + map[u, v];

if (alt < dist[v])

{

dist[v] = alt;

prev[v] = u;

}

return dist;

}

M	T	W	T	F	S	S
« Mar
		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

16 Aug Lý thuyết đồ thị – Thuật toán Dijsktra

No Comments

Post A Comment