Алгоритм Дейкстры

Дата: 9th Июнь 2010. Автор: KAS. Рубрика: Графы
Метки: , ,
0

Алгоритм нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг — метод Дейкстры.

Известны более эффективные алгоритмы для двух важных случаев, а именно: когда веса всех дуг неотрицательны или когда граф бесконтурный. Здесь приведен алгоритм дейктсры.

private void algDeikstra()
        {
            int s = Convert.ToInt32(textBox5.Text) - 1;  //произвольная вершина графа, которая послужит началом пути
            int[] D = new int[n];
            bool fl = true;
            initGraph();                                         //инициализация матрицы смежности
            initMatrixWeight();                               //инициализация матрицы весов
            List V=new List();
 
            if (s < 0 || s >= n)
                return;
 
            for (int i = 0; i < n; i++) D[i] = A[s, i];
 
            for (int i = 0; i < n; i++) V.Add(i);
 
            D[s] = 0;
            int u=0, tmp;
 
            while (V.Count!=0)
            {
                u = V[0];
                tmp=D[V[0]];
                foreach (int i in V)
                {
                    if (D[i] < tmp)
                    {
                        tmp = D[i];
                        u = i;
                    }
                }
 
                V.Remove(u);
 
                foreach (int i in V)
                {
                    D[i] = min(D[i], D[u] + A[u, i]);
                }
 
            }//while
 
            textBox7.Clear();
            for (int i = 0; i < n; i++)
            {
                textBox7.Text += "Кратчайшее расстояние от V" + (s + 1) + " до V" + (i + 1) + " = " + D[i] + "\r\n";
            }
 
        }//algDeikstra()

сложность алгоритма есть O(n2).