|
Axborot texnologiyalari” kafedrasi “MA’lumotlar tuzilmasi va algoritmlari” fanidan amaliy mashg‘ulotlarini bajarish bo‘yicha
|
| bet | 36/39 | | Sana | 12.06.2024 | | Hajmi | 2,32 Mb. | | #262963 |
Bog'liq uslubiy qo\'llanma 3Nazorat savollari:
Grafik ma’lumotlar tuzilishi qnday tasvirlar yordamida namoyish etiladi?
Graflar va daraxtlarning asosiy farqi?
Qanday qilib eng qisqa yo‘l algoritmi aniqlanadi?
Graflarda aniqlangan eng qisqa yo‘l algoritmlarga misollar keltiring?
15-Amaliy mashg‘ulot: Graflarda eng qisqa yo‘lni aniqlash algoritmlari va dasturlarini tuzish.
Ishdan maqsad. Ushbu amaliyot ishida talabalar graflarda eng qisqa yo‘lni aniqlash algoritmlari bilan tanishib chiqishi kerak.
Qo‘yilgan masala. Talabalar topshiriq variantiga mos ravishda graflarda eng qisqa yo‘lni aniqlash algoritmlarini tuzish ko‘nikmasiga ega bo‘lishlari kerak.
Ish tartibi:
Tajriba ishi nazariy ma’lumotlarini o‘rganish;
Berilgan topshiriqning algoritmini ishlab chiqish;
Grafni tuzish va eng qisqa yo‘lni topish.
Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.
Graflarda eng qisqa yo‘lni aniqlash (shortest path problem) algoritmlari va dasturlari ma’lumotlar tarmoqida eng qisqa yo‘lni topish uchun ishlatiladi. Bu algoritm va dasturlar, aloqadorliklarni tahlil qilish, tarmoqni tuzish, va boshqalar kabi turli sabablarni muvaffaqiyatli yechish uchun ishlatiladi. Quyidagi ikkita eng mashhur yo‘lni aniqlash algoritmi bilan tanishasiz:
1. Dijkstra algoritmi:
Dijkstra algoritmi grafdagi eng qisqa yo‘lni aniqlash uchun ishlatiladi. Bu algoritm aloqadorliklar va ularga bo‘lgan masofalarni hisoblash orqali eng qisqa yo‘lni topadi. Algoritm boshlanishi tug‘ilgan tug‘ilgan nuqta va qo‘ng‘iroqning saqlanishi yoki uni qiyoslash bilan boshlanadi. Algoritmi dasturiy til bilan tuzish mumkin.
2. Bellman-Ford algoritmi:
Bellman-Ford algoritmi ham grafdagi eng qisqa yo‘lni aniqlash uchun ishlatiladi. Bu algoritm negativ massivlarga (masofalarga) ega bo‘lgan graflarni ham qo‘llaydi. Bu algoritm odatda negativ massivlarga ega graflar uchun ishlatiladi.
Eng qisqa yo‘lni aniqlash dasturlarini tuzish uchun quyidagi umumiy tartibni muvaffaqiyatli o‘tkazish kerak:
1. Grafni tuzing: Eng avval, berilgan grafdagi aloqadorliklar va masofalarni ifodalovchi grafi tuzing. Grafning tuzilishi va ma’lumotlar qanday ko‘rinishda saqlanishi algoritmlarga bog‘liq bo‘ladi.
2. Dastur oling: Eng qisqa yo‘lni aniqlash uchun talab etilgan dasturni yoki algoritmini tanlang. Yuqoridagi Dijkstra yoki Bellman-Ford algoritmiga qaray olasiz.
3. Boshlanishi belgilang: Algoritmda boshlanishi va tug‘ilgan nuqtani belgilang. Eng qisqa yo‘lni aniqlashning maqsadi nuqta A dan nuqta B gacha yo‘lni topishdan iborat bo‘lishi mumkin.
4. Algoritmnii ishga soling: Tanlagan dasturni ishga soling va eng qisqa yo‘lni aniqlang. Algoritm natijasini olishdan so‘ng yo‘lni ko‘rsating yoki saqlang.
5. Natijani taqdim eting: Natijani ko‘rsatib, yo‘lni ko‘rsating va masofani bildiring. Bu natija grafdagi eng qisqa yo‘lni ifodalaydi.
Bu usullar va tartiblar eng qisqa yo‘lni aniqlash algoritmalarini yaratishda foydali bo‘ladi. Graflarda eng qisqa yo‘lni aniqlash uchun Dijkstra va Bellman-Ford algoritmlari C++ dasturlariga o‘zgartirishsiz qo‘shilarak tuzilishi mumkin. Quyidagi C++ kodlarida o‘zgartirishsiz bu ikkita algoritmni ko‘rsatuvchi misollar keltirilgan. Kodlar o‘zgaruvchilarni, massivlarni va graflarni ishlatadi. Ushbu misollar grafni tuzish, algoritmlarni ishlatish va eng qisqa yo‘lni topishni ko‘rsatadi.
1. Dijkstra algoritmi uchun C++ misoli:
#include
#include
#include
#include
using namespace std;
const int INF = INT_MAX; // Cheksiz sanoat reja.
void dijkstra(vector>>& graph, int start, vector& distance) {
int n = graph.size();
distance.assign(n, INF);
distance[start] = 0;
piority_queue
, vector
>, greater
>> pq;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
int dist_u = pq.top().first;
pq.pop();
if (dist_u != distance[u]) {
continue; // Yo‘lni aniqlash natijasini yangilaymiz.
} for (const pair& edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
if (distance[u] + weight < distance[v]) {
distance[v] = distance[u] + weight;
pq.push({distance[v], v});
} } }
int main() {
int n = 6; // Grafning uchragan yuzasi.
vector> > graph(n);
// Grafni tuzish.
graph[0].push_back({1, 2});
graph[0].push_back({2, 4});
graph[1].push_back({2, 1});
graph[1].push_back({3, 7});
graph[2].push_back({4, 3});
graph[3].push_back({5, 1});
graph[4].push_back({5, 5});
int start = 0;
vector distance;
dijkstra(graph, start, distance);
cout << "Eng qisqa yo‘lni topish natijalari:" << endl;
for (int i = 0; i < n; i++) {
cout << "Nuqta " << start << " dan " << i << " ga: " << distance[i] << endl;
}
return 0;}
2. Bellman-Ford algoritmi uchun C++ misoli:
#include
#include
#include
using namespace std;
const int INF = INT_MAX; // Cheksiz sanoat reja.
struct Edge {
int source, destination, weight;
};void bellmanFord(vector& edges, int n, int start, vector& distance) {
distance.assign(n, INF);
distance[start] = 0;
for (int i = 1; i < n; i++) {
for (const Edge& edge : edges) {
if (distance[edge.source] != INF && distance[edge.source] + edge.weight < distance[edge.destination]) {
distance[edge.destination] = distance[edge.source] + edge.weight;
} } }
int main() {
int n = 6; // Grafning uchragan yuzasi.
vector edges = {
{0, 1, 2},
{0, 2, 4},
{1, 2, 1},
{1, 3, 7},
{2, 4, 3},
{3, 5, 1},
{4, 5, 5} };
int start = 0;
vector distance;
bellmanFord(edges, n, start, distance);
cout << "Eng qisqa yo‘lni topish natijalari:" << endl;
for (int i = 0; i < n; i++) {
cout << "Nuqta " << start << " dan " << i << " ga: " << distance[i] << endl;
} return 0;}
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Axborot texnologiyalari” kafedrasi “MA’lumotlar tuzilmasi va algoritmlari” fanidan amaliy mashg‘ulotlarini bajarish bo‘yicha
|
