O’zbekiston respublikasi axborot texnoloogiyalari va kommunikatsiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnoloogiyalari universiteti muammo, tahlil va yechim fani bo’yicha laboratoriya ishi-1

Amaliy qism: Bu masalani yechishda java dasturlash tilidan foydalandim.
import java.util.*;

public class TransportationProblemSolver {

private static class Node {
String name;
List edges;
int shortestDistance;
boolean visited;
Node previousNode;
public Node(String name) {
this.name = name;
this.edges = new ArrayList<>();
this.shortestDistance = Integer.MAX_VALUE;
this.visited = false;
this.previousNode = null;
}
public void addEdge(Node destination, int weight) {
edges.add(new Edge(destination, weight));
}
}
private static class Edge {
Node destination;
int weight;
public Edge(Node destination, int weight) {
this.destination = destination;
this.weight = weight;
}
}
private static List findShortestPath(Node start, Node end) {
start.shortestDistance = 0;
Queue queue = new PriorityQueue<>(Comparator.comparingInt(node -> node.shortestDistance));
queue.add(start);
while (!queue.isEmpty()) {
Node current = queue.poll();
if (current == end) {
break; // Found the shortest path
}
current.visited = true;
for (Edge edge : current.edges) {
Node next = edge.destination;
int newDistance = current.shortestDistance + edge.weight;
if (!next.visited && newDistance < next.shortestDistance) {
queue.remove(next);
next.shortestDistance = newDistance;
next.previousNode = current;
queue.add(next);
}
}
}
List shortestPath = new ArrayList<>();
Node current = end;
while (current != null) {
shortestPath.add(0, current);
current = current.previousNode;
}
return shortestPath;
}
public static void main(String[] args) {
// Creating nodes
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
// Creating edges
nodeA.addEdge(nodeB, 4);
nodeA.addEdge(nodeC, 2);
nodeB.addEdge(nodeC, 1);
nodeB.addEdge(nodeD, 5);
nodeC.addEdge(nodeD, 8);
nodeC.addEdge(nodeE, 10);
nodeD.addEdge(nodeE, 2);
// Finding the shortest path
List shortestPath = findShortestPath(nodeA, nodeE);
// Displaying the shortest path
System.out.println("Shortest Path:");
for (Node node : shortestPath) {
System.out.print(node.name + " -> ");
}
System.out.println("END");
}
}