Кратчайший путь

Содержание

1. Кратчайший путь
2. Кратчайший путь в неориентированном графе без весов
3. Задан граф с начальной 1-ой и конечной 14-ойНайти кратчайший путь
4. Матричная форма графа
5. Ввод данныхint main() { int G[100][100], //
6. 1 задача – определение числа вершин в
7. Oпределение длины кратчайшего путиint r[100]={0}, // 0
8. 2 задача - Анализ вектора расстоянийif (r[k_p]==0) {cout =r[m]; i++}; m=i;}Jul[1]=n_p;for (i=1; i
9. Кратчайший путь в неориентированном графе с весами
10. Задан граф с начальной 1-ой и конечной 14-ойНайти кратчайший путь
11. Матричная форма графа
12. Ввод данныхint main() { int G[100][100], //
13. 1 задача – определение длины кратчайшего пути
14. Oпределение длины кратчайшего путиint r[100]={-1}, // -1
15. 2 задача - Анализ вектора расстоянийif (r[k_p]==-1) {cout r[m]+G[m][i]; i++}; m=i;}Jul[1]=n_p;for (i=1; i
16. Метод решения такой же как в неориентированном
17. Скачать презентанцию

Кратчайший путь в неориентированном графе без весов

Слайды и текст этой презентации

Слайд 1Кратчайший путь
Старший преподаватель
кафедры теоретической кибернетики
Хадиев Р.М.
КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

Слайд 2Кратчайший путь в неориентированном графе без весов

Слайд 3Задан граф с начальной 1-ой и конечной 14-ой
Найти кратчайший путь

Слайд 4Матричная форма графа

Слайд 5Ввод данных
int main() {
int G[100][100], // граф транспортной сети

I,j,n, // n – число вершин

n_p,k_p; // начало и конец пути
cin >> n >> n_p >> k_p;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
cin >> G[i][j];

Ввод данныхint main() { int G[100][100], // граф транспортной сети I,j,n, // n –

Слайд 61 задача – определение числа вершин в кратчайшего пути до

вершин графа
Длина пути
1 – 1
2,3,4 – 2
5,6,!2 – 3
8,9,14,15 – 4
10,13

– 5
11 – 6

1 задача – определение числа вершин в кратчайшего пути до вершин графаДлина пути1 – 12,3,4 – 25,6,!2

Слайд 7Oпределение длины кратчайшего пути
int r[100]={0}, // 0 – расстояние не

определено
ob[100], // обработанные вершины
a=1,

// вершина из ob , которая обрабатывается
p=2; // пустое место для записи новых вершин
r[n_p]=1; // кратчайший путь в n_p – 1
ob[1]=n_p; //
while a

for (i=0; i if (G[i][ob[a]]==1 & r[i]==0) { //необработанные вершины
r[i]=r[ob[a]]+1;
ob[++p]=I;
}
a++;
}

Oпределение длины кратчайшего путиint r[100]={0}, // 0 – расстояние не определено ob[100], // обработанные вершины

Слайд 82 задача - Анализ вектора расстояний
if (r[k_p]==0) {cout

пути”; return 0;}
int jul[100], // кратчайший путь
m=k_p;

// новая найденная вершина в пути
while (n_p!=m) {
jul[r[m]]=m;
for (i=0;G[i][m]==0 || r[i]>=r[m]; i++};
m=i;
}
Jul[1]=n_p;
for (i=1; i<=r[k_p]; i++) cout << jul[i]<< “ “;

$2 задача - Анализ вектора расстоянийif (r[k_p]==0) {cout =r[m]; i++}; m=i;}Jul[1]=n_p;for (i=1; i$

Слайд 9Кратчайший путь в неориентированном графе с весами

Слайд 10Задан граф с начальной 1-ой и конечной 14-ой
Найти кратчайший путь

Слайд 11Матричная форма графа

Слайд 12Ввод данных
int main() {
int G[100][100], // граф транспортной сети

I,j,n, // n – число вершин

n_p,k_p; // начало и конец пути
cin >> n >> n_p >> k_p;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
cin >> G[i][j];

Слайд 131 задача – определение длины кратчайшего пути до вершин графа
Длина

пути
1 – 0 9 – 15
2 – 3 10 – 20
3 –

5 11 – 32
4 – 5 12 – 12
5 – 13 13 – 24
6 – 12 14 – 18
7 – 8 15 – 14
8 – 16

1 задача – определение длины кратчайшего пути до вершин графаДлина пути1 – 0 9 – 152 – 3 10

Слайд 14Oпределение длины кратчайшего пути
int r[100]={-1}, // -1 – расстояние не

определено
r[n_p]=0; // кратчайший путь в n_p – 0
for (int k=0;

k for (i=0; i for (j=0; j if (G[i][j]>0 & r[i]>=0)
if (r[j]==-1 | r[j]>r[i]+G[[i][j]) r[j]=r[i]+(G[i][j];

$Oпределение длины кратчайшего путиint r[100]={-1}, // -1 – расстояние не определеноr[n_p]=0; // кратчайший путь в n_p –$

Слайд 152 задача - Анализ вектора расстояний
if (r[k_p]==-1) {cout

пути”; return 0;}
int jul[100], // кратчайший путь
m=k_p;

// новая найденная вершина в пути
while (n_p!=m) {
jul[r[m]]=m;
for (i=0;G[i][m]==0 || r[i]>r[m]+G[m][i]; i++};
m=i;
}
Jul[1]=n_p;
for (i=1; i<=r[k_p]; i++) cout << jul[i]<< “ “;

$2 задача - Анализ вектора расстоянийif (r[k_p]==-1) {cout r[m]+G[m][i]; i++}; m=i;}Jul[1]=n_p;for (i=1; i$