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 dijkstra(self, start_vertex_data):
        start_vertex = self.vertex_data.index(start_vertex_data)
        distances = [float('inf')] * self.size
        distances[start_vertex] = 0
        visited = [False] * self.size

for _ in range(self.size):
            min_distance = float('inf')
            u = None
            for i in range(self.size):
                if not visited[i] and distances[i] < min_distance:
                    min_distance = distances[i]
                    u = i

if u is None:
                break

visited[u] = True

for v in range(self.size):
                if self.adj_matrix[u][v] != 0 and not visited[v]:
                    alt = distances[u] + self.adj_matrix[u][v]
                    if alt < distances[v]:
                        distances[v] = alt

return distances

g = Graph(7)

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_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')

g.add_edge(3, 0, 4)  # D - A, weight 5
g.add_edge(3, 4, 2)  # D - E, weight 2
g.add_edge(0, 2, 3)  # A - C, weight 3
g.add_edge(0, 4, 4)  # A - E, weight 4
g.add_edge(4, 2, 4)  # E - C, weight 4
g.add_edge(4, 6, 5)  # E - G, weight 5
g.add_edge(2, 5, 5)  # C - F, weight 5
g.add_edge(2, 1, 2)  # C - B, weight 2
g.add_edge(1, 5, 2)  # B - F, weight 2
g.add_edge(6, 5, 5)  # G - F, weight 5

# Dijkstra's algorithm from D to all vertices
print("Dijkstra's Algorithm starting from vertex D:\n")
distances = g.dijkstra('D')
for i, d in enumerate(distances):
    print(f"Shortest distance from D to {g.vertex_data[i]}: {d}")

#Python

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

typedef struct {
    int **adj_matrix;
    char *vertex_data;
    int size;
} Graph;

Graph* create_graph(int size) {
    Graph *g = malloc(sizeof(Graph));
    g->size = size;
    g->adj_matrix = malloc(size * sizeof(int *));
    for (int i = 0; i < size; i++) {
        g->adj_matrix[i] = calloc(size, sizeof(int));
    }
    g->vertex_data = malloc(size * sizeof(char));
    return g;
}

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

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

int min_distance(int distances[], bool visited[], int size) {
    int min = INT_MAX, min_index = -1;
    for (int v = 0; v < size; v++) {
        if (!visited[v] && distances[v] <= min) {
            min = distances[v];
            min_index = v;
        }
    }
    return min_index;
}

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

int distances[g->size];
    bool visited[g->size];
    for (int i = 0; i < g->size; i++) {
        distances[i] = INT_MAX;
        visited[i] = false;
    }
    distances[start_vertex] = 0;

for (int i = 0; i < g->size - 1; i++) {
        int u = min_distance(distances, visited, g->size);
        visited[u] = true;

for (int v = 0; v < g->size; v++) {
            if (!visited[v] && g->adj_matrix[u][v] && distances[u] != INT_MAX && distances[u] + g->adj_matrix[u][v] < distances[v]) {
                distances[v] = distances[u] + g->adj_matrix[u][v];
            }
        }
    }

printf("Dijkstra's Algorithm starting from vertex %c:\n\n", start_vertex_data);
    for (int i = 0; i < g->size; i++) {
        printf("Shortest distance from %c to %c: %d\n", start_vertex_data, g->vertex_data[i], distances[i]);
    }
}

void free_graph(Graph *g) {
    for (int i = 0; i < g->size; i++) {
        free(g->adj_matrix[i]);
    }
    free(g->adj_matrix);
    free(g->vertex_data);
    free(g);
}

int main() {
    Graph *g = create_graph(7);

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_vertex_data(g, 5, 'F');
    add_vertex_data(g, 6, 'G');

add_edge(g, 3, 0, 4); // D - A, weight 4
    add_edge(g, 3, 4, 2); // D - E, weight 2
    add_edge(g, 0, 2, 3); // A - C, weight 3
    add_edge(g, 0, 4, 4); // A - E, weight 4
    add_edge(g, 4, 2, 4); // E - C, weight 4
    add_edge(g, 4, 6, 5); // E - G, weight 5
    add_edge(g, 2, 5, 5); // C - F, weight 5
    add_edge(g, 2, 1, 2); // C - B, weight 2
    add_edge(g, 1, 5, 2); // B - F, weight 2
    add_edge(g, 6, 5, 5); // G - F, weight 5

dijkstra(g, 'D');

free_graph(g);
    return 0;
}

//C

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

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

public int[] dijkstra(String startVertexData) {
            int startVertex = findIndex(startVertexData);
            int[] distances = new int[size];
            boolean[] visited = new boolean[size];

for (int i = 0; i < size; i++) {
                distances[i] = Integer.MAX_VALUE;
            }
            distances[startVertex] = 0;

for (int i = 0; i < size; i++) {
                int u = minDistance(distances, visited);
                if (u == -1) break;

visited[u] = true;
                for (int v = 0; v < size; v++) {
                    if (!visited[v] && adjMatrix[u][v] != 0 && distances[u] != Integer.MAX_VALUE) {
                        int newDist = distances[u] + adjMatrix[u][v];
                        if (newDist < distances[v]) {
                            distances[v] = newDist;
                        }
                    }
                }
            }
            return distances;
        }

private int findIndex(String data) {
            for (int i = 0; i < size; i++) {
                if (vertexData[i].equals(data)) {
                    return i;
                }
            }
            return -1;
        }

private int minDistance(int[] distances, boolean[] visited) {
            int min = Integer.MAX_VALUE, minIndex = -1;

for (int v = 0; v < size; v++) {
                if (!visited[v] && distances[v] <= min) {
                    min = distances[v];
                    minIndex = v;
                }
            }
            return minIndex;
        }
    }

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

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

g.addEdge(3, 0, 4); // D - A, weight 4
        g.addEdge(3, 4, 2); // D - E, weight 2
        g.addEdge(0, 2, 3); // A - C, weight 3
        g.addEdge(0, 4, 4); // A - E, weight 4
        g.addEdge(4, 2, 4); // E - C, weight 4
        g.addEdge(4, 6, 5); // E - G, weight 5
        g.addEdge(2, 5, 5); // C - F, weight 5
        g.addEdge(2, 1, 2); // C - B, weight 2
        g.addEdge(1, 5, 2); // B - F, weight 2
        g.addEdge(6, 5, 5); // G - F, weight 5

// Dijkstra's algorithm from D to all vertices
        System.out.println("Dijkstra's Algorithm starting from vertex D:\n");
        int[] distances = g.dijkstra("D");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("Shortest distance from D to " + g.vertexData[i] + ": " + distances[i]);
        }
    }
}

//Java