12-Amaliy ish Mavzu: Bog’langan graflarda marshrutlar, ularni narxi(masofasi) bo’yicha baholash. Xasis algortimlar. Eng qisqa marshrutlarni aniqlash algoritmi. Uni variantlar soni bo’yicha xajmini baholash

Amalga oshirish

Shunday qilib Deykstra algoritmi iteratsiyadan iborat. Harbir iteratsiyada qiymat eng kichik bo’lgan hali ko’rilmagan uch tanlanadi. Bu uch ko’rilgan uchlar ro’yxatiga kiritladi va bu uchdan chiquvchi harbir uch bo’yicha relaksatsiya tekshiriladi va har bir qirra bo’yicha massiv qiymatini yaxshilashga harakat qilinadi.
Algoritmning ishlash vaqti quyidagicha hisoblaymiz:

• 
  marta hali ko’rilmagan uchlar orasida eng kichik li uchni topamiz, ya’ni uch ichidan.
  
• 
  marta relaksatsiyaga urinidh amalga oshiriladi
  

Bu amallarni oddiy amalga oshirishda, uchni izlash uchun operatsiya, bitta relaksatsiya uchun esa— operatsiya ketadi. Algoritmning natijaviy asimptotikasi:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;


public class EnQisqaYol {

static final double INF = 1e9;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int from = sc.nextInt();
int to = sc.nextInt();
double[][]a = new double[n][n];
double[]d = new double[n];
Arrays.fill(d, INF);
d[from] = 0;
int[]p = new int[n];
boolean[]used = new boolean[n];
for (int i = 1; i <= n; i++) {
int v = -1;
for (int j = 0; j < n; j++) {
if (!used[j] && (v==-1 || d[j] < d[v]))
v = j;
}
if (Math.abs(d[v]-INF) < 5) {
break;
}
used[v] = true;
for (int j = 0; j < n; j++) {
if (a[v][j] > 0 && d[v]+a[v][j] < d[j]) {
p[j] = v;
d[j] = d[v]+a[v][j];
}
}
}
ArrayList path = new ArrayList();
if (Math.abs(d[to]-INF) < 5) {
System.out.println("Yo'l mavjud emas");
}
else {
int cur = to;
while (true) {
path.add(cur+1);
if (cur==from)
break;
cur = p[cur];
}
Collections.reverse(path);
System.out.println(path);
}
}
}
Cpp dagi kodi:
#include
#include
using namespace std;
int main() {
int n ;
cin>>n;
int from,to;
cin>>from;
cin>>to;
to--; from--;
double a [n][n];
for(int i=0; ifor(int j=0; jcin>>a[i][j];
double d [n];
bool used [n];
int INF=1000000000;
for(int i=0; i d[i]= INF; used[i]=false;
}

d[from] = 0;

int p [n];

for (int i = 1; i <= n; i++) {

int v = -1;
for (int j = 0; j < n; j++) {
if (!used[j] && (v==-1 || d[j] < d[v]))
v = j;
}

used[v] = true;

for (int j = 0; j < n; j++) {
if (a[v][j] > 0 && d[v]+a[v][j] < d[j]) {
p[j] = v;
d[j] = d[v]+a[v][j];
}
}
}
cout< for(int i=0; i cout< cout<}
Natija:
N=6; from=1; to=6 bo’lsa:
6
1
6
0 7 9 0 0 14
7 0 10 15 0 0
9 10 0 11 0 2
0 15 11 0 6 0
0 0 0 6 0 9
14 0 2 0 9 0

1-Topshiriq
763. 64 MB
Given a connected weighted undirected graph.
Consider a pair of vertices, the distance between which is maximum among all pairs of vertices. The distance between them is called the diameter of the graph. Eccentricity of vertex v is the maximum distance from a vertex v to the other vertices of the graph. Radius of a graph is the smallest of the eccentricities of the vertices.
Find the diameter and radius of the graph.
Input
The first line of the input only number: N (1 ≤ N ≤ 100) - the number of vertices. The next N lines by N numbers - the adjacency matrix of the graph, where -1 means no edges between vertices, and any non-negative number - the presence of an edge weight. On the main diagonal of the matrix is always zero; weight edges do not exceed 1000.