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, end_vertex_data):
        start_vertex = self.vertex_data.index(start_vertex_data)
        end_vertex = self.vertex_data.index(end_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 or u == end_vertex:
                print(f"Breaking out of loop. Current vertex: {self.vertex_data[u]}")
                print(f"Distances: {distances}")
                break

visited[u] = True
            print(f"Visited vertex: {self.vertex_data[u]}")

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[end_vertex], self.get_path(predecessors, start_vertex_data, end_vertex_data)

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(10)

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_vertex_data(7, 'H')
g.add_vertex_data(8, 'I')
g.add_vertex_data(9, 'J')

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
g.add_edge(6, 8, 4)  # G - I, weight 4
g.add_edge(6, 7, 5)  # G - H, weight 5
g.add_edge(8, 9, 2)  # I - J, weight 2

print("Dijkstra's Algorithm, from vertex D to F:\n")
distance, path = g.dijkstra('D','F')
print(f"Path: {path}, Distance: {distance}")

#Python

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

#define SIZE 10

typedef struct Graph {
    int adjMatrix[SIZE][SIZE];
    char* vertexData[SIZE];
} Graph;

void addEdge(Graph* g, int u, int v, int weight) {
    g->adjMatrix[u][v] = weight;
    g->adjMatrix[v][u] = weight;
}

void addVertexData(Graph* g, int vertex, char* data) {
    g->vertexData[vertex] = data;
}

// Function to find the vertex with minimum distance value
int minDistance(int dist[], int sptSet[]) {
    // Initialize min value
    int min = INT_MAX, min_index;
    for (int v = 0; v < SIZE; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void printPath(Graph* g, int parent[], int j) {
    // Base case: If j is the source vertex, return
    if (j == -1 || parent[j] == -1) {
        return;
    }

printPath(g, parent, parent[j]);
    printf("->%s", g->vertexData[j]);
}

// Function that implements Dijkstra's algorithm
void dijkstra(Graph* g, int src, int target) {
    int dist[SIZE];
    int sptSet[SIZE];
    int parent[SIZE];
    for (int i = 0; i < SIZE; i++) {
        parent[src] = -1;
        dist[i] = INT_MAX;
        sptSet[i] = 0;
    }
    dist[src] = 0;
    for (int count = 0; count < SIZE - 1; count++) {
        int u = minDistance(dist, sptSet);

// Check if the algorithm is complete
        if (u == -1 || u == target) {
            printf("Breaking out of loop. Current vertex: %s\n", g->vertexData[u]);
            printf("Distances: [");
            for (int i = 0; i < SIZE; i++) {
                if(i > 0) printf(", ");
                printf("%d", dist[i]);
            }
            printf("]\n");
            break;
        }

printf("Visited vertex: %s\n", g->vertexData[u]);
        
        sptSet[u] = 1;
        for (int v = 0; v < SIZE; v++)
            if (!sptSet[v] && g->adjMatrix[u][v] && dist[u] + g->adjMatrix[u][v] < dist[v]) {
                parent[v] = u;
                dist[v] = dist[u] + g->adjMatrix[u][v];
            }
    }
    printf("Path: ");
    if (src != target) {
        printf("%s", g->vertexData[src]); // Print source vertex
        printPath(g, parent, target);     // Start path printing from next vertex
    } else {
        printf("%s", g->vertexData[src]); // Print only the source vertex if it is the target
    }
    printf(", Distance: %d\n", dist[target]);
}

int main() {
    Graph g = {0};

// Initialize vertex data
    addVertexData(&g, 0, "A");
    addVertexData(&g, 1, "B");
    addVertexData(&g, 2, "C");
    addVertexData(&g, 3, "D");
    addVertexData(&g, 4, "E");
    addVertexData(&g, 5, "F");
    addVertexData(&g, 6, "G");
    addVertexData(&g, 7, "H");
    addVertexData(&g, 8, "I");
    addVertexData(&g, 9, "J");

// Initialize edges
    addEdge(&g, 3, 0, 4); // D - A, weight 4
    addEdge(&g, 3, 4, 2); // D - E, weight 2
    addEdge(&g, 0, 2, 3); // A - C, weight 3
    addEdge(&g, 0, 4, 4); // A - E, weight 4
    addEdge(&g, 4, 2, 4); // E - C, weight 4
    addEdge(&g, 4, 6, 5); // E - G, weight 5
    addEdge(&g, 2, 5, 5); // C - F, weight 5
    addEdge(&g, 2, 1, 2); // C - B, weight 2
    addEdge(&g, 1, 5, 2); // B - F, weight 2
    addEdge(&g, 6, 5, 5); // G - F, weight 5
    addEdge(&g, 6, 8, 4); // G - I, weight 4
    addEdge(&g, 6, 7, 5); // G - H, weight 5
    addEdge(&g, 8, 9, 2); // I - J, weight 2

// Run Dijkstra's algorithm from D to F
    printf("Dijkstra's Algorithm, from vertex D to F:\n\n");
    dijkstra(&g, 3, 5);

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

public void addVertexData(int vertex, String data) {
            vertexData[vertex] = data;
        }

public String dijkstra(String startVertexData, String endVertexData) {
            int[] predecessors = new int[size];
            Arrays.fill(predecessors, -1);
            int startVertex = Arrays.asList(vertexData).indexOf(startVertexData);
            int endVertex = Arrays.asList(vertexData).indexOf(endVertexData);
            int[] distances = new int[size];
            Arrays.fill(distances, Integer.MAX_VALUE);
            distances[startVertex] = 0;
            boolean[] visited = new boolean[size];

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

if (u == endVertex) {
                    System.out.println("Breaking out of loop. Current vertex: " + vertexData[u]);
                    System.out.println("Distances: " + Arrays.toString(distances));
                    break;
                }
        
                visited[u] = true;
                System.out.println("Visited vertex: " + vertexData[u]);
        
                for (int v = 0; v < size; v++) {
                    if (!visited[v] && 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;
                    }
                }
            }

String shortestPath = getPath(distances, predecessors, startVertex, endVertex);
            return "Path: " + shortestPath + ", Distance: " + distances[endVertex];
        }

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 String getPath(int[] distances, int[] predecessors, int startVertex, int endVertex) {
            if (endVertex == -1 || distances[endVertex] == Integer.MAX_VALUE) {
                return "No path";
            }
        
            StringBuilder path = new StringBuilder();
            for(int vertex = endVertex; vertex != -1; vertex = predecessors[vertex]) {
                path.insert(0, vertexData[vertex]);
                if(vertex != startVertex) {
                    path.insert(0, "->");
                }
            }
            return path.toString();
        }
    }

public static void main(String[] args) {
        Graph g = new Graph(10);
        
        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.addVertexData(7, "H");
        g.addVertexData(8, "I");
        g.addVertexData(9, "J");

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
        g.addEdge(6, 8, 4); // G - I, weight 4
        g.addEdge(6, 7, 5); // G - H, weight 5
        g.addEdge(8, 9, 2); // I - J, weight 2

System.out.println("Dijkstra's Algorithm, from vertex D to F:\n");
        String result = g.dijkstra("D", "F");
        System.out.println(result);
    }
}