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):

#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++) {

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;

​