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]}")

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, -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:")
distances = g.bellman_ford('D')
for i, d in enumerate(distances):
    print(f"Distance from D to {g.vertex_data[i]}: {d}")
    
#Python

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_VERTEX_DATA 10 // Maximum length of vertex data string

typedef struct {
    int size;
    int **adjMatrix;
    char **vertexData;
} Graph;

Graph* createGraph(int size) {
    Graph *g = (Graph*)malloc(sizeof(Graph));
    g->size = size;

// Allocate memory for adjacency matrix
    g->adjMatrix = (int**)malloc(size * sizeof(int*));
    for (int i = 0; i < size; i++) {
        g->adjMatrix[i] = (int*)calloc(size, sizeof(int));
    }

// Allocate memory for vertex data
    g->vertexData = (char**)malloc(size * sizeof(char*));
    for (int i = 0; i < size; i++) {
        g->vertexData[i] = (char*)calloc(MAX_VERTEX_DATA, sizeof(char));
    }

return g;
}

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;
        //g->adjMatrix[v][u] = weight; // For undirected graph
    }
}

void addVertexData(Graph *g, int vertex, const char *data) {
    if (vertex >= 0 && vertex < g->size) {
        strncpy(g->vertexData[vertex], data, MAX_VERTEX_DATA - 1);
    }
}

void bellmanFord(Graph *g, const char *startVertexData) {
    int startVertex = -1;
    for (int i = 0; i < g->size; i++) {
        if (strcmp(g->vertexData[i], startVertexData) == 0) {
            startVertex = i;
            break;
        }
    }

if (startVertex == -1) {
        printf("Start vertex not found\n");
        return;
    }

int distances[g->size];
    for (int i = 0; i < g->size; i++) {
        distances[i] = INT_MAX;
    }
    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] != 0 && distances[u] != INT_MAX &&
                    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]);
                }
            }
        }
    }

// Print distances
    for (int i = 0; i < g->size; i++) {
        printf("Distance from %s to %s: %d\n", startVertexData, g->vertexData[i], distances[i]);
    }
}

void freeGraph(Graph *g) {
    if (g != NULL) {
        // Free each row of the adjacency matrix
        for (int i = 0; i < g->size; i++) {
            free(g->adjMatrix[i]);
        }
        // Free the adjacency matrix itself
        free(g->adjMatrix);

// Free each vertex data string
        for (int i = 0; i < g->size; i++) {
            free(g->vertexData[i]);
        }
        // Free the vertex data array
        free(g->vertexData);

// Finally, free the graph structure
        free(g);
    }
}

int main() {
    Graph *g = createGraph(5);

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, -3); // C -> A, weight -3
    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

printf("\nThe Bellman-Ford Algorithm starting from vertex D:\n");
    bellmanFord(g, "D");

freeGraph(g); //Freeing up memory

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(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;
                //adjMatrix[v][u] = weight; // For undirected graph
            }
        }

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

public int[] bellmanFord(String startVertexData) {
            int startVertex = -1;
            for (int i = 0; i < size; i++) {
                if (vertexData[i].equals(startVertexData)) {
                    startVertex = i;
                    break;
                }
            }
            if (startVertex == -1) {
                throw new IllegalArgumentException("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]);
                        }
                    }
                }
            }

return 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");

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

// Running the Bellman-Ford algorithm from D to all vertices
        System.out.println("\nThe Bellman-Ford Algorithm starting from vertex D:");
        int[] distances = g.bellmanFord("D");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("Distance from D to " + g.vertexData[i] + ": " + distances[i]);
        }
    }
}

//Java