#include using namespace std; #define INF 0x3f3f3f3f struct Vertex { int x, y; Vertex(int x, int y) : x(x), y(y) {} }; typedef pair iPair; class Graph { int V; vector vertices; vector> edgeWeights; public: Graph(int V); void addVertex(int x, int y); void addEdge(int u, int v); double euclideanDistance(const Vertex& u, const Vertex& v); void shortestPath(int src); }; Graph::Graph(int V) { this->V = V; edgeWeights.resize(V, vector(V, INF)); } void Graph::addVertex(int x, int y) { vertices.emplace_back(x, y); } void Graph::addEdge(int u, int v) { double weight = euclideanDistance(vertices[u], vertices[v]); edgeWeights[u][v] = weight; edgeWeights[v][u] = weight; } double Graph::euclideanDistance(const Vertex& u, const Vertex& v) { return sqrt(pow(u.x - v.x, 2) + pow(u.y - v.y, 2)); } void Graph::shortestPath(int src) { priority_queue, greater> pq; vector dist(V, INF); pq.push(make_pair(0, src)); dist[src] = 0; while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (int v = 0; v < V; ++v) { if (edgeWeights[u][v] != INF && dist[v] > dist[u] + edgeWeights[u][v]) { dist[v] = dist[u] + edgeWeights[u][v]; pq.push(make_pair(dist[v], v)); } } } printf("Vertex Distance from Source\n"); for (int i = 0; i < V; ++i) printf("Vertex %d: %.2lf\n", i, dist[i]); int destination; cout << "Enter your preferred destination vertex: "; cin >> destination; if (dist[destination] == INF) { cout << "No path exists from source to destination." << endl; } else { cout << "Shortest distance from source to destination: " << dist[destination] << endl; } } int main() { int V = 4; Graph g(V); g.addVertex(1, 1); g.addVertex(1, 5); g.addVertex(5, 1); g.addVertex(5, 5); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(0, 3); g.addEdge(1, 3); g.addEdge(0, 2); int source; cout << "Enter the source vertex: "; cin >> source; cout << endl; g.shortestPath(source); cout<<"\n"; return 0; }