W3Schools 線上編輯器 - W3Schools 教學

Python

Java

class Graph:
    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, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = weight
            #self.adj_matrix[v][u] = weight  # For undirected graph

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)
        distances = [float('inf')] * self.size
        distances[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 distances[u] + self.adj_matrix[u][v] < distances[v]:
                            distances[v] = distances[u] + self.adj_matrix[u][v]
                            print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")

# Negative cycle detection
        for 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] < distances[v]:
                        return (True, None)  # Indicate a negative cycle was found

return (False, distances)  # Indicate no negative cycle and return distances

g = Graph(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, weight 4
g.add_edge(3, 2, 7)  # D -> C, weight 7
g.add_edge(3, 4, 3)  # D -> E, weight 3
g.add_edge(0, 2, 4)  # A -> C, weight 4
g.add_edge(2, 0, -9) # C -> A, weight -9
g.add_edge(0, 4, 5)  # A -> E, weight 5
g.add_edge(4, 2, 3)  # E -> C, weight 3
g.add_edge(1, 2, -4) # B -> C, weight -4
g.add_edge(4, 1, 2)  # E -> B, weight 2

# Running the Bellman-Ford algorithm from D to all vertices
print("\nThe Bellman-Ford Algorithm starting from vertex D:")
negative_cycle, distances = g.bellman_ford('D')
if not negative_cycle:
    for i, d in enumerate(distances):
        print(f"Distance from D to {g.vertex_data[i]}: {d}")
else:
    print("Negative weight cycle detected. Cannot compute shortest paths.")
    
#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];
    int size;
} Graph;

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] = weight;
    }
}

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;
        }
    }
    return -1;
}

int bellmanFord(Graph *g, char *startVertexData, int *distances) {
    int startVertex = findVertexIndex(g, startVertexData);
    if (startVertex == -1) return -1;

for (int i = 0; i < g->size; i++) {
        distances[i] = INF;
    }
    distances[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] && distances[u] != INF &&
                    distances[u] + g->adjMatrix[u][v] < distances[v]) {
                    distances[v] = distances[u] + g->adjMatrix[u][v];
                    printf("Relaxing edge %s->%s, Updated distance to %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] && distances[u] != INF &&
                distances[u] + g->adjMatrix[u][v] < distances[v]) {
                return 0; // Negative cycle detected
            }
        }
    }

return 1; // No negative cycle detected
}

int main() {
    Graph 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, weight 4
    addEdge(&g, 3, 2, 7);  // D -> C, weight 7
    addEdge(&g, 3, 4, 3);  // D -> E, weight 3
    addEdge(&g, 0, 2, 4);  // A -> C, weight 4
    addEdge(&g, 2, 0, -9); // C -> A, weight -9
    addEdge(&g, 0, 4, 5);  // A -> E, weight 5
    addEdge(&g, 4, 2, 3);  // E -> C, weight 3
    addEdge(&g, 1, 2, -4); // B -> C, weight -4
    addEdge(&g, 4, 1, 2);  // E -> B, weight 2

int distances[MAX_VERTICES];
    printf("The Bellman-Ford Algorithm starting from vertex D:\n");
    if (bellmanFord(&g, "D", distances)) {
        for (int i = 0; i < g.size; i++) {
            if (distances[i] != INF) {
                printf("Distance from D to %s: %d\n", g.vertexData[i], distances[i]);
            } else {
                printf("Distance from D to %s: Infinity\n", g.vertexData[i]);
            }
        }
    } else {
        printf("Negative weight cycle detected. Cannot compute the shortest paths.\n");
    }

return 0;

}

//C

import java.util.Arrays;

public class Main {
    static class Graph {
        private int[][] adjMatrix;
        private String[] vertexData;
        private int size;

public Graph(int size) {
            this.size = size;
            this.adjMatrix = new int[size][size];
            this.vertexData = new String[size];
            Arrays.fill(this.vertexData, ""); // Initialize with empty strings
        }

public void addEdge(int u, int v, int weight) {
            if (0 <= u && u < size && 0 <= v && v < size) {
                adjMatrix[u][v] = weight;
            }
        }

public void addVertexData(int vertex, String data) {
            if (0 <= vertex && vertex < size) {
                vertexData[vertex] = data;
            }
        }

public Result bellmanFord(String startVertexData) {
            int startVertex = -1;
            for (int i = 0; i < size; i++) {
                if (vertexData[i].equals(startVertexData)) {
                    startVertex = i;
                    break;
                }
            }
            if (startVertex == -1) {
                return new Result(true, null); // Start vertex not found
            }

int[] distances = new int[size];
            Arrays.fill(distances, Integer.MAX_VALUE);
            distances[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 && distances[u] != Integer.MAX_VALUE &&
                            distances[u] + adjMatrix[u][v] < distances[v]) {
                            distances[v] = distances[u] + adjMatrix[u][v];
                            System.out.println("Relaxing edge " + vertexData[u] + "->" + vertexData[v] + ", Updated distance to " + vertexData[v] + ": " + distances[v]);
                        }
                    }
                }
            }

// Check for negative weight cycle
            for (int u = 0; u < size; u++) {
                for (int v = 0; v < size; v++) {
                    if (adjMatrix[u][v] != 0 && distances[u] != Integer.MAX_VALUE &&
                        distances[u] + adjMatrix[u][v] < distances[v]) {
                        return new Result(true, null);
                    }
                }
            }

return new Result(false, distances);
        }
    }

static class Result {
        boolean hasNegativeCycle;
        int[] distances;

public Result(boolean hasNegativeCycle, int[] distances) {
            this.hasNegativeCycle = hasNegativeCycle;
            this.distances = distances;
        }
    }

public static void main(String[] args) {
        Graph g = new Graph(5);

g.addVertexData(0, "A");
        g.addVertexData(1, "B");
        g.addVertexData(2, "C");
        g.addVertexData(3, "D");
        g.addVertexData(4, "E");

// Add edges
        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);

// Run Bellman-Ford algorithm
        System.out.println("\nThe Bellman-Ford Algorithm starting from vertex D:");
        Result result = g.bellmanFord("D");
        if (!result.hasNegativeCycle) {
            for (int i = 0; i < result.distances.length; i++) {
                System.out.println("Distance from D to " + g.vertexData[i] + ": " + result.distances[i]);
            }
        } else {
            System.out.println("Negative weight cycle detected. Cannot compute shortest paths.");
        }
    }
}

//Java

Python 結果

C 結果

Java 結果

Bellman-Ford 演算法從頂點 D 開始
鬆弛邊 D->A，更新到 A 的距離：4
鬆弛邊 D->C，更新到 C 的距離：7
鬆弛邊 D->E，更新到 E 的距離：3
鬆弛邊 E->B，更新到 B 的距離：5
鬆弛邊 E->C，更新到 C 的距離：6
鬆弛邊 B->C，更新到 C 的距離：1
正在鬆弛邊 C->A，A 的更新距離：-8
正在鬆弛邊 A->C，C 的更新距離：-4
正在鬆弛邊 A->E，E 的更新距離：-3
正在鬆弛邊 C->A，A 的更新距離：-13
正在鬆弛邊 E->B，B 的更新距離：-1
正在鬆弛邊 A->C，C 的更新距離：-9
正在鬆弛邊 A->E，E 的更新距離：-8
正在鬆弛邊 C->A，A 的更新距離：-18
正在鬆弛邊 E->B，B 的更新距離：-6
檢測到負權重環。無法計算最短路徑。