Dijkstra algaritmi:
C# dagi kodi:
Program.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace topshiriq12
{
class Program
{
static void Main(string[] args)
{
/* Keling, misol yarataylik Yuqorida muhokama qilingan grafik */
int[,] graph = new int[,]
{
{ 0, 61, 22, 74, 30, 24, 63 },
{ 61, 0, 6, 36, 88, 96, 98 },
{ 22, 6, 0, 86, 47, 5, 88 },
{ 74, 36, 86, 0, 69, 11, 88 },
{ 30, 88, 47, 69, 0, 95, 64 },
{ 24, 96, 5, 11, 95, 0, 88 },
{ 63, 98, 88, 88, 64, 88, 0 }
};
GFG t = new GFG();
t.dijkstra(graph, 0);
Console.ReadKey();
}
}
class GFG
{
// ni topish uchun yordamchi dastur
// minimal masofaga ega cho'qqi
// qiymat, cho'qqilar to'plamidan
// hali eng qisqacha kiritilmagan
// yo'l daraxti
static int V = 7;
int minDistance(int[] dist,
bool[] sptSet)
{
// Minimal qiymatni ishga tushiring
int min = int.MaxValue, min_index = -1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
return min_index;
}
// Chop etish uchun yordamchi dastur
// tuzilgan masofa massivi
public void printSolution(int[] dist, int n)
{
Console.Write("Vertex Distance "
+ "from Source\n");
for (int i = 0; i < V; i++)
Console.Write(i + " \t\t " + dist[i] + "\n");
}
// Dijkstrani amalga oshiradigan funksiya
// yagona manbali eng qisqa yo'l algoritmi
// qo'shnilik yordamida ifodalangan grafik uchun
// matritsa tasviri
public void dijkstra(int[,] graph, int src)
{
int[] dist = new int[V]; // Chiqish massivi. dist[i]
// eng qisqasini ushlab turadi
// src dan i gacha bo'lgan masofa
// sptSet[i] agar vertex bo'lsa rost bo'ladi
// i eng qisqa yo'lga kiritilgan
// daraxt yoki eng qisqa masofa
// src to i yakunlandi
bool[] sptSet = new bool[V];
// Barcha masofalarni quyidagicha boshlang
// INFINITE va stpSet[] noto'g'ri
for (int i = 0; i < V; i++)
{
dist[i] = int.MaxValue;
sptSet[i] = false;
}
// Manba cho'qqisining masofasi
// o'zidan har doim 0 bo'ladi
dist[src] = 0;
// Barcha cho'qqilar uchun eng qisqa yo'lni toping
for (int count = 0; count < V - 1; count++)
{
// Minimal masofa cho'qqisini tanlang
// hali bo'lmagan cho'qqilar to'plamidan
// qayta ishlangan. u har doim ga teng
// src birinchi iteratsiyada.
int u = minDistance(dist, sptSet);
// Tanlangan cho'qqini qayta ishlangan deb belgilang
sptSet[u] = true;
// Qo'shnisining dist qiymatini yangilang
// tanlangan cho'qqining cho'qqilari.
for (int v = 0; v < V; v++)
// Dist[v] ni faqat tizimda bo'lmasa yangilang
// sptSet, u dan chekka bor
// dan v gacha va yo'lning umumiy og'irligi
// src dan v orqali u gacha kichikroq
// dist[v] ning joriy qiymatidan
if (!sptSet[v] && graph[u, v] != 0 &&
dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v])
dist[v] = dist[u] + graph[u, v];
}
// tuzilgan masofa massivini chop eting
printSolution(dist, V);
}
}
}
|
