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
        predecessors = [None] * 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]
                            predecessors[v] = u
                            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, None)  # Indicate a negative cycle was found

return (False, distances, predecessors)  # Indicate no negative cycle and return distances
    
    def get_path(self, predecessors, start_vertex, end_vertex):
        path = []
        current = self.vertex_data.index(end_vertex)
        while current is not None:
            path.insert(0, self.vertex_data[current])
            current = predecessors[current]
            if current == self.vertex_data.index(start_vertex):
                path.insert(0, start_vertex)
                break
        return '->'.join(path)

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, -3) # C -> A, weight -3
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, predecessors = g.bellman_ford('D')
if not negative_cycle:
    for i, d in enumerate(distances):
        if d != float('inf'):
            path = g.get_path(predecessors, 'D', g.vertex_data[i])
            print(f"{path}, Distance: {d}")
        else:
            print(f"No path from D to {g.vertex_data[i]}, Distance: Infinity")
else:
    print("Negative weight cycle detected. Cannot compute shortest paths.")
    
#Python

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>  // Include <limits.h> for INT_MAX and INT_MIN
#include <string.h>  // Include <string.h> for string operations

#define MAX_SIZE 100  // Define the maximum size for the graph

// Structure to represent a graph
typedef struct {
    int adj_matrix[MAX_SIZE][MAX_SIZE];  // Adjacency matrix
    int size;                            // Number of vertices
    char vertex_data[MAX_SIZE];          // Data for each vertex
} Graph;

// Function to initialize the graph
void init_graph(Graph *g, int size) {
    g->size = size;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            g->adj_matrix[i][j] = 0;  // Initialize adjacency matrix to 0
        }
        g->vertex_data[i] = '\0';    // Initialize vertex data to empty
    }
}

// Function to add an edge to the graph
void add_edge(Graph *g, int u, int v, int weight) {
    if (u >= 0 && u < g->size && v >= 0 && v < g->size) {
        g->adj_matrix[u][v] = weight;
        // For an undirected graph, also set g->adj_matrix[v][u] = weight;
    }
}

// Function to add data to a vertex
void add_vertex_data(Graph *g, int vertex, char data) {
    if (vertex >= 0 && vertex < g->size) {
        g->vertex_data[vertex] = data;
    }
}

int bellman_ford(Graph *g, char start_vertex_data, int distances[], int predecessors[]) {
    int start_vertex = -1;
    for (int i = 0; i < g->size; i++) {
        if (g->vertex_data[i] == start_vertex_data) {
            start_vertex = i;
            break;
        }
    }

for (int i = 0; i < g->size; i++) {
        distances[i] = INT_MAX;  // Use INT_MAX from <limits.h>
        predecessors[i] = -1;
    }

distances[start_vertex] = 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->adj_matrix[u][v] != 0) {
                    if (distances[u] != INT_MAX && distances[u] + g->adj_matrix[u][v] < distances[v]) {
                        distances[v] = distances[u] + g->adj_matrix[u][v];
                        predecessors[v] = u;
                        printf("Relaxing edge %c->%c, Updated distance to %c: %d\n", g->vertex_data[u], g->vertex_data[v], g->vertex_data[v], distances[v]);
                    }
                }
            }
        }
    }

// Negative cycle detection
    for (int u = 0; u < g->size; u++) {
        for (int v = 0; v < g->size; v++) {
            if (g->adj_matrix[u][v] != 0) {
                if (distances[u] != INT_MAX && distances[u] + g->adj_matrix[u][v] < distances[v]) {
                    return 1;  // Indicate a negative cycle was found
                }
            }
        }
    }

return 0;  // Indicate no negative cycle
}

// Function to get the shortest path from start_vertex_data to end_vertex_data
void get_path(Graph *g, int predecessors[], char start_vertex_data, char end_vertex_data, char path[]) {
    int path_index = 0;
    int current = -1;

for (int i = 0; i < g->size; i++) {
        if (g->vertex_data[i] == end_vertex_data) {
            current = i;
            break;
        }
    }

while (current != -1) {
        path[path_index++] = g->vertex_data[current];
        current = predecessors[current];
        if (current != -1 && g->vertex_data[current] == start_vertex_data) {
            path[path_index++] = start_vertex_data;
            break;
        }
    }

// Reverse the path and add arrows
    char reversed_path[MAX_SIZE];
    int reversed_index = 0;
    for (int i = path_index - 1; i >= 0; i--) {
        reversed_path[reversed_index++] = path[i];
        if (i > 0) {
            reversed_path[reversed_index++] = '-';
            reversed_path[reversed_index++] = '>';
        }
    }
    reversed_path[reversed_index] = '\0';

strcpy(path, reversed_path);
}

int main() {
    // Create and initialize the graph
    Graph g;
    init_graph(&g, 5);

add_vertex_data(&g, 0, 'A');
    add_vertex_data(&g, 1, 'B');
    add_vertex_data(&g, 2, 'C');
    add_vertex_data(&g, 3, 'D');
    add_vertex_data(&g, 4, 'E');

add_edge(&g, 3, 0, 4);  // D -> A, weight 4
    add_edge(&g, 3, 2, 7);  // D -> C, weight 7
    add_edge(&g, 3, 4, 3);  // D -> E, weight 3
    add_edge(&g, 0, 2, 4);  // A -> C, weight 4
    add_edge(&g, 2, 0, -3); // C -> A, weight -3
    add_edge(&g, 0, 4, 5);  // A -> E, weight 5
    add_edge(&g, 4, 2, 3);  // E -> C, weight 3
    add_edge(&g, 1, 2, -4); // B -> C, weight -4
    add_edge(&g, 4, 1, 2);  // E -> B, weight 2

int distances[MAX_SIZE];     // Declare distances array in main
    int predecessors[MAX_SIZE];  // Declare predecessors array in main

// Running the Bellman-Ford algorithm from D to all vertices
    printf("\nThe Bellman-Ford Algorithm starting from vertex D:\n");
    int negative_cycle = bellman_ford(&g, 'D', distances, predecessors);  // Pass distances and predecessors arrays
    if (!negative_cycle) {
        for (int i = 0; i < g.size; i++) {
            if (g.vertex_data[i] != '\0') {
                char path[MAX_SIZE];
                get_path(&g, predecessors, 'D', g.vertex_data[i], path);
                if (path[0] != '\0') {
                    printf("%s, Distance: %d\n", path, distances[i]);
                } else {
                    printf("No path from D to %c, Distance: Infinity\n", g.vertex_data[i]);
                }
            }
        }
    } else {
        printf("Negative weight cycle detected. Cannot compute 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];
        }

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

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

public Result bellmanFord(String startVertexData) {
            int startVertex = findVertex(startVertexData);
            int[] distances = new int[size];
            Integer[] predecessors = new Integer[size];
            Arrays.fill(distances, Integer.MAX_VALUE);
            Arrays.fill(predecessors, null);
            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];
                            predecessors[v] = u;
                            System.out.printf("Relaxing edge %s->%s, Updated distance to %s: %d%n",
                                              vertexData[u], vertexData[v], vertexData[v], distances[v]);
                        }
                    }
                }
            }

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, null);
                    }
                }
            }

return new Result(false, distances, predecessors);
        }

private int findVertex(String vertexData) {
            for (int i = 0; i < this.vertexData.length; i++) {
                if (this.vertexData[i].equals(vertexData)) {
                    return i;
                }
            }
            return -1; // Vertex not found
        }

public String getPath(Integer[] predecessors, String startVertex, String endVertex) {
            if (predecessors == null) {
                return "Path not available";
            }
        
            StringBuilder path = new StringBuilder();
            int current = findVertex(endVertex);
        
            // Handle cases where endVertex is not found or has no path
            if (current == -1 || predecessors[current] == null) {
                return "No path from " + startVertex + " to " + endVertex;
            }
        
            while (current != -1) {
                path.insert(0, this.vertexData[current]);
                Integer pred = predecessors[current];
                if (pred != null && pred != findVertex(startVertex)) {
                    path.insert(0, "->");
                    current = pred;
                } else {
                    if (pred != null) {
                        path.insert(0, startVertex + "->");
                    }
                    break;
                }
            }
            return path.toString();
        }        
    }

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

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

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");
    
        g.addEdge(3, 0, 4);  // D -> A, weight 4
        g.addEdge(3, 2, 7);  // D -> C, weight 7
        g.addEdge(3, 4, 3);  // D -> E, weight 3
        g.addEdge(0, 2, 4);  // A -> C, weight 4
        g.addEdge(2, 0, -3); // C -> A, weight -3
        g.addEdge(0, 4, 5);  // A -> E, weight 5
        g.addEdge(4, 2, 3);  // E -> C, weight 3
        g.addEdge(1, 2, -4); // B -> C, weight -4
        g.addEdge(4, 1, 2);  // E -> B, weight 2
    
        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++) {
                if (result.distances[i] != Integer.MAX_VALUE) {
                    String startVertexData = "D"; // Start vertex as a string
                    String endVertexData = g.vertexData[i]; // Convert end vertex index to string
                    String path = g.getPath(result.predecessors, startVertexData, endVertexData);
                    System.out.println(path + ", Distance: " + result.distances[i]);
                } else {
                    System.out.println("No path from D to " + g.vertexData[i] + ", Distance: Infinity");
                }
            }
        } else {
            System.out.println("Negative weight cycle detected. Cannot compute shortest paths.");
        }
    }

}

//Java