2015-06-05
391
1. Граф сети в соответствии с заданием.
2. Пошаговое описание работы матричного метода при определении длин кратчайших путей.
3. Пошаговое описание работы метода Флойда при определении кратчайших путей.
4. Дерево кратчайших путей от заданной вершины ко всем остальным вершинам, построенное с помощью матрицы кратчайших путей.
Варианты заданий
1. Число узлов определяется по формуле N = 5 + i mod 3, где i – номер варианта.
2. Номер подварианта определяется по формуле j = i mod 7.
3. Расстояния между узлами приведены в таблице.
4. Номер узла, от которого строится дерево кратчайших путей определяется по формуле I = (i + 1) mod N. Соответствие номеров узлов именам узлов: 0-A, 1-B, 2-С и т.д.
| Число узлов | Подвариант | Расстояние между узлами |
| N=5 | AB=30; BD=40+; AC=50+; CD=10; EA=35; ED=25+; BC=20; CE=40+ | |
| AC=20; AD=30+; BE=10+; BD=25; CB=85; CD=15+; | ||
| AB=30+; BD=20; AC=5; CB=15; CD=20+; EA=25; CE=15; DE=40+ | ||
| AB=20+; BD=30+; CA=40; CB=10+; CD=15+; AE=35; EC=15; ED=40 | ||
| AE=5+; AD=60; BE=80; CB=10; DE=50+; EC=35; | ||
| AB=30; BD=30+; CA=60; CD=15+; CB=10+; AE=30+; CE=25+; DE=40+ | ||
| AE=60+; BC=10+; CA=25; CD=15; CE=30+; DE=20+; EB=90; | ||
| N=6 | AB=30; BC=15+; AD=20+; DC=20+; BD=15+; DF=25+; CE=25+; ED=10; EF=40+; DF=25+; FA=15 | |
| AF=25+; AB=10; BC=30+; CF=75+; DE=50+; EB=40; FE=15; | ||
| AB=20; BC=30; AD=20+; DC=20+; CE=10+; DE=35; DF=10; EF=40+; FA=15 | ||
| BA=40; BC=10+; AD=30+; DB=35+; DC=5+; DE=20+; EС=65+; AF=25; FE=20; | ||
| AF=25; BA=35; BE=70+; BD=10; BC=45+; CE=20+; DE=90+; EF=5+; | ||
| AB=40+; AD=35; BC=10+; CD=35+; DE=35+; EB=10; EF=15; FA=5; | ||
| BA=35; BC=10+; AD=40; DB=10; CD=25+; AF=60; DF=10+; CE=70+; DE=15; EF=30+ | ||
| N=7 | AB=20+; BC=30; AD=30; BD=20+; DC=15; CE=35; DE=20+; DF=10+; FE=15; FG=15+; DG=15+; GA=35 | |
| AE=10+; BC=20+; BD=20+; CD=60+; CF=70+; DG=15+; DE=40+; FG=5+; GA=25; | ||
| AB=30; BC=40+; DA=35; DB=10+; DC=85; CE=35; ED=20; EF=5+; FD=15+; GF=30; GD=30+; AG=45+; | ||
| AG=50+; AE=15; AC=15+; BC=10; CF=15; DB=10; DA=40; DE=20+; EF=35+; FG=60+; | ||
| AD=60+; BA=10; BF=65+; BC=20+; CG=5+; CE=70+; DC=15; ED=20; EF=35; FG=25; | ||
| AB=15+; BC=30+; BD=20; AD=15+; DC=20+; CE=35+; DE=40+; DF=10; FE=20+; GF=10+; GD=50+; AG=35+ | ||
| BA=20; BC=15; BD=25+; DC=30+; DA=25+; CE=35+; ED=40; FE=30+; DF=15; FG=5+; GD=15+; GA=25 |
Примечание:
|
|
|
1. Знак «=», например, AB= означает, что направление передачи будет от узла A к узлу B.
2. Знак «+» означает двустороннюю передачу (соответствующая дуга не имеет стрелок).
Контрольные вопросы
1. Какие бывают критерии для оценки длины пути?
2. Что такое кратчайший путь?
3. В чём смысл соотношения кратчайшего пути и его под путей?
4. В чём заключается теоретическая основа матричного метода?
5. Что позволяет найти матричный метод?
6. Что позволяет найти метод Флойда?
7. Как формируется матрица непосредственных связей для матричного метода?
8. В чём смысл перехода от классического умножения матриц к умножению матриц в матричном методе?
9. Как формируется дистанционная матрица?
10. В чём заключается теоретическая основа метода Флойда?
11. В чём суть отличия матрицы непосредственных связей для матричного метода и метода Флойда?
12. Как формируется матрица кратчайших путей при методе Флойда?
13. Что такое дерево кратчайших путей?
[1] Текст дополнительно редактировал Волков П.Л.
