Run ❯
Get your
own
website
×
Change Orientation
Change Theme, Dark/Light
Go to Spaces
Python
C
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
#include
#include
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
Python result:
C result:
Java result:
Dijkstra's Algorithm starting from vertex D:
D->A, Distance: 4
D->E->C->B, Distance: 8
D->E->C, Distance: 6
D, Distance: 0
D->E, Distance: 2
D->E->C->B->F, Distance: 10
D->E->G, Distance: 7
Dijkstra's Algorithm starting from vertex D:
D->A, Distance: 4
D->E->C->B, Distance: 8
D->E->C, Distance: 6
D, Distance: 0
D->E, Distance: 2
D->E->C->B->F, Distance: 10
D->E->G, Distance: 7
Dijkstra's Algorithm starting from vertex D:
D->A, Distance: 4
D->E->C->B, Distance: 8
D->E->C, Distance: 6
D, Distance: 0
D->E, Distance: 2
D->E->C->B->F, Distance: 10
D->E->G, Distance: 7