Кратчайший путь - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Кратчайший путь. Доклад-сообщение содержит 16 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 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 – число вершин 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

Описание слайда:

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

Слайд 7

$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++; }$

Описание слайда:

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

$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]<< “ “;$

Описание слайда:

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

Описание слайда:

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

Слайд 10

Описание слайда:

Задан граф с начальной 1-ой и конечной 14-ой

Слайд 11

Описание слайда:

Матричная форма графа

Слайд 12

Описание слайда:

Слайд 13

Описание слайда:

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

Слайд 14

$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];$

Описание слайда:

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

$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]<< “ “;$

Описание слайда:

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]<< “ “;