Trình chỉnh sửa thử của Example.com.vn

Python

Java

Đồ thị lớp: def __init__(self, size): self.adj_matrix = [[0] * size for _ in range(size)] self.size = size self.vertex_data = [''] * size def add_edge(self, u , v, trọng lượng): if 0 <= u < self.size và 0 <= v < self.size: self.adj_matrix[u][v] = trọng lượng #self.adj_matrix[v][u] = trọng lượng # For đồ thị vô hướng def add_vertex_data(self, vertex, data): if 0 <= vertex < self.size: self.vertex_data[vertex] = data def bellman_ford(self, start_vertex_data): start_vertex = self.vertex_data.index(start_vertex_data) khoảng cách = [float('inf')] * khoảng cách self.size[start_vertex] = 0 for i in range(self.size - 1): for u in range(self.size): for v in range(self.size): if self.adj_matrix[u][v] != 0: if khoảng cách[u] + self.adj_matrix[u][v] < khoảng cách[v]: khoảng cách[v] = khoảng cách[u] + self.adj_matrix[u ][v] print(f"Cạnh thư giãn {self.vertex_data[u]}->{self.vertex_data[v]}, Đã cập nhật khoảng cách lên {self.vertex_data[v]}: {distances[v]}") # Phát hiện chu kỳ âm cho u in range(self.size): for v in range(self.size): if self.adj_matrix[u][v] != 0: if distances[u] + self.adj_matrix[u][ v] < khoảng cách[v]: return (Đúng, Không) # Cho biết đã tìm thấy chu trình âm return (Sai, khoảng cách) # Cho biết không có chu kỳ âm và khoảng cách trả về g = Đồ thị(5) g.add_vertex_data(0, 'A' ) g.add_vertex_data(1, 'B') g.add_vertex_data(2, 'C') g.add_vertex_data(3, 'D') g.add_vertex_data(4, 'E') g.add_edge(3, 0, 4 ) # D -> A, trọng lượng 4 g.add_edge(3, 2, 7) # D -> C, trọng lượng 7 g.add_edge(3, 4, 3) # D -> E, trọng lượng 3 g.add_edge(0 , 2, 4) # A -> C, trọng số 4 g.add_edge(2, 0, -9) # C -> A, trọng lượng -9 g.add_edge(0, 4, 5) # A -> E, trọng lượng 5 g.add_edge(4, 2, 3) # E -> C, trọng số 3 g.add_edge(1, 2, -4) # B -> C, trọng số -4 g.add_edge(4, 1, 2) # E -> B, trọng số 2 # Chạy thuật toán Bellman-Ford từ D đến tất cả các đỉnh print("\nThuật toán Bellman-Ford bắt đầu từ đỉnh D:") âm_cycle, khoảng cách = g.bellman_ford('D') nếu không phải âm_cycle : for i, d in enumerate(distances): print(f"Khoảng cách từ D đến {g.vertex_data[i]}: {d}") else: print("Đã phát hiện chu kỳ trọng số âm. Không thể tính toán đường đi ngắn nhất.") #Python

#include <stdio.h> #include <stdlib.h> #include <limits.h> #include <string.h> #define MAX_VERTICES 5 #define INF INT_MAX typedef struct { int adjMatrix[MAX_VERTICES][MAX_VERTICES]; char* vertexData[MAX_VERTICES]; kích thước int; } Đồ thị; void initGraph(Graph *g, int size) { g->size = size; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { g->adjMatrix[i][j] = 0; } g->vertexData[i] = NULL; } } void addEdge(Graph *g, int u, int v, int Weight) { if (u >= 0 && u < g->size && v >= 0 && v < g->size) { g->adjMatrix [u][v] = trọng lượng; } } void addVertexData(Graph *g, int vertex, char *data) { if (vertex >= 0 && vertex < g->size) { g->vertexData[vertex] = data; } } int findVertexIndex(Graph *g, char *vertexData) { for (int i = 0; i < g->size; i++) { if (g->vertexData[i] && strcmp(g->vertexData[i] , vertexData) == 0) { return i; } } trả về -1; } int bellmanFord(Graph *g, char *startVertexData, int *distances) { int startVertex = findVertexIndex(g, startVertexData); if (startVertex == -1) trả về -1; for (int i = 0; i < g->size; i++) { distances[i] = INF; } khoảng cách[startVertex] = 0; for (int i = 0; i < g->size - 1; i++) { for (int u = 0; u < g->size; u++) { for (int v = 0; v < g->size; v++) { if (g->adjMatrix[u][v] && khoảng cách[u] != INF && khoảng cách[u] + g->adjMatrix[u][v] < khoảng cách[v]) { khoảng cách[v] = khoảng cách[u] + g->adjMatrix[u][v]; printf("Cạnh thư giãn %s->%s, Đã cập nhật khoảng cách thành %s: %d\n", g->vertexData[u], g->vertexData[v], g->vertexData[v], distances[ v]); } } } } for (int u = 0; u < g->size; u++) { for (int v = 0; v < g->size; v++) { if (g->adjMatrix[u][v] && khoảng cách[u] != INF && khoảng cách[u] + g->adjMatrix[u][v] < khoảng cách[v]) { return 0; // Đã phát hiện chu kỳ âm } } } return 1; // Không phát hiện thấy chu kỳ âm } int main() { Đồ thị g; initGraph(&g, MAX_VERTICES); addVertexData(&g, 0, "A"); addVertexData(&g, 1, "B"); addVertexData(&g, 2, "C"); addVertexData(&g, 3, "D"); addVertexData(&g, 4, "E"); addEdge(&g, 3, 0, 4); // D -> A, trọng số 4 addEdge(&g, 3, 2, 7); // D -> C, trọng số 7 addEdge(&g, 3, 4, 3); // D -> E, trọng số 3 addEdge(&g, 0, 2, 4); // A -> C, trọng số 4 addEdge(&g, 2, 0, -9); // C -> A, trọng số -9 addEdge(&g, 0, 4, 5); // A -> E, trọng số 5 addEdge(&g, 4, 2, 3); // E -> C, trọng số 3 addEdge(&g, 1, 2, -4); // B -> C, trọng số -4 addEdge(&g, 4, 1, 2); // E -> B, trọng số 2 int khoảng cách[MAX_VERTICES]; printf("Thuật toán Bellman-Ford bắt đầu từ đỉnh D:\n"); if (bellmanFord(&g, "D", khoảng cách)) { for (int i = 0; i < g.size; i++) { if (distances[i] != INF) { printf("Khoảng cách từ D đến %s : %d\n", g.vertexData[i], khoảng cách[i]); } else { printf("Khoảng cách từ D đến %s: Vô cực\n", g.vertexData[i]); } } } else { printf("Đã phát hiện chu kỳ trọng số âm. Không thể tính toán đường đi ngắn nhất.\n"); } trả về 0; } //C

nhập java.util.Arrays; lớp công khai Chính { lớp tĩnh Đồ thị { int riêng tư [] [] adjMatrix; Chuỗi riêng tư[] vertexData; kích thước int riêng tư; Đồ thị công khai (kích thước int) { this.size = size; this.adjMatrix = new int[size][size]; this.vertexData = Chuỗi mới[size]; Arrays.fill(this.vertexData, ""); // Khởi tạo với chuỗi trống } public void addEdge(int u, int v, int Weight) { if (0 <= u && u < size && 0 <= v && v < size) { adjMatrix[u][v] = cân nặng; } } public void addVertexData(int vertex, String data) { if (0 <= vertex && vertex < size) { vertexData[vertex] = data; } } kết quả công khai bellmanFord(String startVertexData) { int startVertex = -1; for (int i = 0; i < size; i++) { if (vertexData[i].equals(startVertexData)) { startVertex = i; phá vỡ; } } if (startVertex == -1) { trả về kết quả mới (true, null); // Không tìm thấy đỉnh bắt đầu } int[] distances = new int[size]; Arrays.fill(khoảng cách, Integer.MAX_VALUE); khoảng cách[startVertex] = 0; for (int i = 0; i < size - 1; i++) { for (int u = 0; u < size; u++) { for (int v = 0; v < size; v++) { if (adjMatrix[u] [v] != 0 && khoảng cách[u] != Integer.MAX_VALUE && khoảng cách[u] + adjMatrix[u][v] < khoảng cách[v]) { khoảng cách[v] = khoảng cách[u] + adjMatrix[u] [v]; System.out.println("Cạnh thư giãn " + vertexData[u] + "->" + vertexData[v] + ", Đã cập nhật khoảng cách thành " + vertexData[v] + ": " + distances[v]); } } } } // Kiểm tra chu kỳ trọng số âm for (int u = 0; u < size; u++) { for (int v = 0; v < size; v++) { if (adjMatrix[u][v] != 0 && khoảng cách[u] != Integer.MAX_VALUE && khoảng cách[u] + adjMatrix[u][v] < khoảng cách[v]) { trả về kết quả mới(true, null); } } } trả về Kết quả mới (sai, khoảng cách); } } lớp tĩnh Kết quả { boolean hasNegativeCycle; khoảng cách int[]; kết quả công khai (boolean hasNegativeCycle, int[] khoảng cách) { this.hasNegativeCycle = hasNegativeCycle; this.distances = khoảng cách; } } public static void main(String[] args) { Đồ thị g = Đồ thị mới(5); g.addVertexData(0, "A"); g.addVertexData(1, "B"); g.addVertexData(2, "C"); g.addVertexData(3, "D"); g.addVertexData(4, "E"); // Thêm các cạnh g.addEdge(3, 0, 4); g.addEdge(3, 2, 7); g.addEdge(3, 4, 3); g.addEdge(0, 2, 4); g.addEdge(2, 0, -9); g.addEdge(0, 4, 5); g.addEdge(4, 2, 3); g.addEdge(1, 2, -4); g.addEdge(4, 1, 2); // Chạy thuật toán Bellman-Ford System.out.println("\nThuật toán Bellman-Ford bắt đầu từ đỉnh D:"); Kết quả result = g.bellmanFord("D"); if (!result.hasNegativeCycle) { for (int i = 0; i < result.distances.length; i++) { System.out.println("Khoảng cách từ D đến " + g.vertexData[i] + ": " + result.distances[i]); } } else { System.out.println("Đã phát hiện chu kỳ trọng số âm. Không thể tính toán đường đi ngắn nhất."); } } } //Java

Kết quả Python:

Kết quả C:

Kết quả Java:

Thuật toán Bellman-Ford bắt đầu từ đỉnh D:
Cạnh thư giãn D->A, Khoảng cách được cập nhật thành A: 4
Cạnh thư giãn D->C, Khoảng cách được cập nhật lên C: 7
Cạnh thư giãn D->E, Cập nhật khoảng cách lên E: 3
Cạnh thư giãn E->B, Khoảng cách được cập nhật lên B: 5
Cạnh thư giãn E->C, Khoảng cách được cập nhật lên C: 6
Cạnh thư giãn B->C, Khoảng cách được cập nhật lên C: 1
Cạnh thư giãn C->A, Khoảng cách được cập nhật thành A: -8
Cạnh thư giãn A->C, Khoảng cách được cập nhật lên C: -4
Cạnh thư giãn A->E, Khoảng cách được cập nhật lên E: -3
Cạnh thư giãn C->A, Khoảng cách được cập nhật thành A: -13
Cạnh thư giãn E->B, Khoảng cách được cập nhật lên B: -1
Cạnh thư giãn A->C, Khoảng cách được cập nhật lên C: -9
Cạnh thư giãn A->E, Cập nhật khoảng cách lên E: -8
Cạnh thư giãn C->A, Khoảng cách được cập nhật thành A: -18
Cạnh thư giãn E->B, Khoảng cách được cập nhật lên B: -6
Đã phát hiện chu kỳ trọng số âm. Không thể tính toán đường đi ngắn nhất

Thuật toán Bellman-Ford bắt đầu từ đỉnh D:
Cạnh thư giãn D->A, Khoảng cách được cập nhật thành A: 4
Cạnh thư giãn D->C, Khoảng cách được cập nhật lên C: 7
Cạnh thư giãn D->E, Cập nhật khoảng cách lên E: 3
Cạnh thư giãn E->B, Khoảng cách được cập nhật lên B: 5
Cạnh thư giãn E->C, Khoảng cách được cập nhật lên C: 6
Cạnh thư giãn B->C, Khoảng cách được cập nhật lên C: 1
Cạnh thư giãn C->A, Khoảng cách được cập nhật thành A: -8
Cạnh thư giãn A->C, Khoảng cách được cập nhật lên C: -4
Cạnh thư giãn A->E, Khoảng cách được cập nhật lên E: -3
Cạnh thư giãn C->A, Khoảng cách được cập nhật thành A: -13
Cạnh thư giãn E->B, Khoảng cách được cập nhật lên B: -1
Cạnh thư giãn A->C, Khoảng cách được cập nhật lên C: -9
Cạnh thư giãn A->E, Khoảng cách được cập nhật lên E: -8
Cạnh thư giãn C->A, Khoảng cách được cập nhật thành A: -18
Cạnh thư giãn E->B, Khoảng cách được cập nhật lên B: -6
Đã phát hiện chu kỳ trọng số âm. Không thể tính toán đường đi ngắn nhất