Kompyuter injeneringi

Bellman-Ford algoritmi dasturi:

import java.util.*;

class Graph {
private int vertexCount;
private List> adjacencyList;

public Graph(int vertexCount) {

this.vertexCount = vertexCount;
adjacencyList = new ArrayList<>(vertexCount);
for (int i = 0; i < vertexCount; i++) {
adjacencyList.add(new ArrayList<>());
}
}

public void addEdge(int source, int destination, int weight) {

adjacencyList.get(source).add(new Edge(destination, weight));
}

public int[] dijkstra(int source) {

int[] distances = new int[vertexCount];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[source] = 0;

PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));

pq.add(new Node(source, 0));

while (!pq.isEmpty()) {

Node current = pq.poll();
int vertex = current.vertex;
int distance = current.distance;

if (distance > distances[vertex]) {

continue;
}

for (Edge edge : adjacencyList.get(vertex)) {

int newDistance = distance + edge.weight;
if (newDistance < distances[edge.destination]) {
distances[edge.destination] = newDistance;
pq.add(new Node(edge.destination, newDistance));
}
}
}

return distances;

}

private static class Edge {

private int destination;
private int weight;

public Edge(int destination, int weight) {

this.destination = destination;
this.weight = weight;
}
}

private static class Node {

private int vertex;
private int distance;

public Node(int vertex, int distance) {

this.vertex = vertex;
this.distance = distance;
}
}
}

public class DijkstraAlgorithm {

public static void main(String[] args) {
Graph graph = new Graph(6);

graph.addEdge(0, 1, 2);

graph.addEdge(0, 2, 4);
graph.addEdge(1, 3, 7);
graph.addEdge(1, 4, 3);
graph.addEdge(2, 4, 1);
graph.addEdge(3, 4, 5);
graph.addEdge(3, 5, 2);

int[] distances = graph.dijkstra(0);

System.out.println("Shortest distances from source vertex 0:");
for (int i = 0; i < distances.length; i++) {
System.out.println("Vertex " + i + ": " + distances[i]);
}
}
}