Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
16 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
399.87 kB
Просмотров:
67
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Кратчайший путь](/documents_6/785989cd455e9de2469cfaceb33bae5c/img0.jpg)
Содержание слайда: Кратчайший путь
№2 слайд![Кратчайший путь в](/documents_6/785989cd455e9de2469cfaceb33bae5c/img1.jpg)
Содержание слайда: Кратчайший путь
в неориентированном
графе без весов
№3 слайд![Задан граф с начальной -ой и](/documents_6/785989cd455e9de2469cfaceb33bae5c/img2.jpg)
Содержание слайда: Задан граф
с начальной 1-ой и конечной 14-ой
№4 слайд![Матричная форма графа](/documents_6/785989cd455e9de2469cfaceb33bae5c/img3.jpg)
Содержание слайда: Матричная форма графа
№5 слайд![Ввод данных int main int G ,](/documents_6/785989cd455e9de2469cfaceb33bae5c/img4.jpg)
Содержание слайда: Ввод данных
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];
№6 слайд![задача определение числа](/documents_6/785989cd455e9de2469cfaceb33bae5c/img5.jpg)
Содержание слайда: 1 задача – определение числа вершин в кратчайшего пути до вершин графа
№7 слайд![Oпределение длины кратчайшего](/documents_6/785989cd455e9de2469cfaceb33bae5c/img6.jpg)
Содержание слайда: Oпределение длины кратчайшего пути
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<p do {
for (i=0; i<n; i++) // ищем связанные с ob[a]
if (G[i][ob[a]]==1 & r[i]==0) { //необработанные вершины
r[i]=r[ob[a]]+1;
ob[++p]=I;
}
a++;
}
№8 слайд![задача - Анализ вектора](/documents_6/785989cd455e9de2469cfaceb33bae5c/img7.jpg)
Содержание слайда: 2 задача - Анализ вектора расстояний
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]<< “ “;
№9 слайд![Кратчайший путь в](/documents_6/785989cd455e9de2469cfaceb33bae5c/img8.jpg)
Содержание слайда: Кратчайший путь
в неориентированном
графе с весами
№10 слайд![Задан граф с начальной -ой и](/documents_6/785989cd455e9de2469cfaceb33bae5c/img9.jpg)
Содержание слайда: Задан граф
с начальной 1-ой и конечной 14-ой
№11 слайд![Матричная форма графа](/documents_6/785989cd455e9de2469cfaceb33bae5c/img10.jpg)
Содержание слайда: Матричная форма графа
№12 слайд![Ввод данных int main int G ,](/documents_6/785989cd455e9de2469cfaceb33bae5c/img11.jpg)
Содержание слайда: Ввод данных
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];
№13 слайд![задача определение длины](/documents_6/785989cd455e9de2469cfaceb33bae5c/img12.jpg)
Содержание слайда: 1 задача – определение длины кратчайшего пути до вершин графа
№14 слайд![Oпределение длины кратчайшего](/documents_6/785989cd455e9de2469cfaceb33bae5c/img13.jpg)
Содержание слайда: Oпределение длины кратчайшего пути
int r[100]={-1}, // -1 – расстояние не определено
r[n_p]=0; // кратчайший путь в n_p – 0
for (int k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; 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];
№15 слайд![задача - Анализ вектора](/documents_6/785989cd455e9de2469cfaceb33bae5c/img14.jpg)
Содержание слайда: 2 задача - Анализ вектора расстояний
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]<< “ “;
№16 слайд![Метод решения такой же как в](/documents_6/785989cd455e9de2469cfaceb33bae5c/img15.jpg)
Содержание слайда: Метод решения такой же как в неориентированном
графе с весами