Задача о критическом пути в графе

  • 05 нояб. 2011 г.
  • 490 Слова
Изм.
Лист
№ докум.
Подпись
Дата
Лист

1.3 Задача о критическом пути в графе.
Постановка задачи: Дан ориентированный граф, в котором отсутствуют контуры и каждой дуге которого приписан весСтруктура графа определяется следующим условием: он имеет дугу, связывающую вершины Xi c вершиной Xj, если в исходных условиях задан вес
Необходимо найти путь от заданной начальной вершины (истока) кзаданной конечной вершине (стоку), имеющий наибольшую длину, равную сумме весов дуг, входящих в этот путь.
Исходные данные:
с(1,2) = 4; с(1,6) = 8; с(1,7) = 18; с(2,3) = 11; с(2,7) = 4; с(2,8) = 17;с(2,9) = 12;
с(3,4) =15; с(3,9) = 8; с(4,12) = 7; с(5,7) = 13; с(5,11) = 11; с(5,13) = 17;
с(6,5) = 4; с(6,7) = 2; с(7,8) = 18; с(7,10) = 7; с(7,11) = 5; с(7,13) = 14; с(8,4) = 3;
с(8,10) = 9;с(8,12) = 3; с(9,4) = 16; с(9,8) = 5; с(10,12) = 4; с(10,13) = 8;
с(11,13) = 9; с(12,13) = 3.
Решение:
Таблица 1
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12 | X13 |
X1 | |4 | | | | 8 | 18 | | | | | | |
X2 | | | 11 | | | | 4 | 17 | 12 | | | | |
X3 | | | | 15 | | | | | 8 | | | | |
X4 | | | | | | | | | | | | 7 | |
X5 | || | | | | 13 | | | | 11 | | 17 |
X6 | | | | | 4 | | 2 | | | | | | |
X7 | | | | | | | | 18 | | 7 | 5 | | 14 |
X8 | | | | 3 | | | | | | 9 | | 3 | |
X9 || | | 16 | | | | 5 | | | | | |
X10 | | | | | | | | | | | | 4 | 3 |
X11 | | | | | | | | | | | | | 9 |
X12 | | | | | | | | | | | | | 3 |
X13 | || | | | | | | | | | | |
Заносим исходные данные в таблицу (табл. 1). На основе исходных данных строим граф (рис. 1). Затем , используя алгоритм [1], ищем критический путь в графе.Перенумеровываем вершины графа. Вершины получает номер , затем следующий номер присваевается любому неперенумерованному событию, для которого все предшествующие события перенумерованны.
Затем...
tracking img