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
        predecessors = [None] * 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
                        predecessors[v] = u
        
        return distances, predecessors

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)  # Join the vertices with '->'

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

#include <stdio.h>
#include <stdlib.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;
    }
}

void dijkstra(Graph *g, int start_vertex, int *distances, int *predecessors) {
    int visited[g->size];
    for (int i = 0; i < g->size; i++) {
        distances[i] = INT_MAX;
        visited[i] = 0;
        predecessors[i] = -1;
    }
    distances[start_vertex] = 0;

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

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];
                predecessors[v] = u;
            }
        }
    }
}

void print_path(Graph *g, int *predecessors, int start_vertex, int end_vertex) {
    int stack[g->size], top = -1;
    int current = end_vertex;
    while (current != -1) {
        stack[++top] = current;
        current = predecessors[current];
    }

while (top != -1) {
        printf("%c", g->vertex_data[stack[top--]]);
        if (top != -1) printf("->");
    }
}

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

int distances[g->size], predecessors[g->size];
    dijkstra(g, 3, distances, predecessors);

printf("Dijkstra's Algorithm starting from vertex D:\n\n");
    for (int i = 0; i < g->size; i++) {
        print_path(g, predecessors, 3, i);
        printf(", Distance: %d\n", distances[i]);
    }

// Free the graph
    for (int i = 0; i < g->size; i++) free(g->adj_matrix[i]);
    free(g->adj_matrix);
    free(g->vertex_data);
    free(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 (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 String getShortestPath(int startVertex, int endVertex) {
            int[] distances = new int[size];
            int[] predecessors = new int[size];
            boolean[] visited = new boolean[size];
            for (int i = 0; i < size; i++) {
                distances[i] = Integer.MAX_VALUE;
                predecessors[i] = -1;
            }
            distances[startVertex] = 0;

for (int i = 0; i < size; i++) {
                int u = -1;
                for (int j = 0; j < size; j++) {
                    if (!visited[j] && (u == -1 || distances[j] < distances[u])) {
                        u = j;
                    }
                }

visited[u] = true;

for (int v = 0; v < size; v++) {
                    if (adjMatrix[u][v] != 0 && !visited[v]) {
                        int alt = distances[u] + adjMatrix[u][v];
                        if (alt < distances[v]) {
                            distances[v] = alt;
                            predecessors[v] = u;
                        }
                    }
                }
            }

StringBuilder path = new StringBuilder();
            for (int at = endVertex; at != -1; at = predecessors[at]) {
                path.insert(0, vertexData[at] + (path.length() > 0 ? "->" : ""));
            }

return path.toString() + ", Distance: " + distances[endVertex];
        }
    }

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

System.out.println("Dijkstra's Algorithm starting from vertex D: \n");
        for (int i = 0; i < g.size; i++) {
            System.out.println(g.getShortestPath(3, i));
        }
    }
}

//Java