Hello, I have this Dijkstra’s exercise. could you help me to solve it? In C# and C++ 2. A weighted graph is a graph that has a numeric (for example, integer) label w(e) associated with eachedge e, called the weight of edge e. Let G be a weighted graph. The length (or weight) of a path is the sumof the weights of the edges of P. That is, if P = ((vo, V1), (V1, v2), ...,(vk-1, VR)) then the length of P,denoted w(P), is defined as:w(P) =((*+'a 'la))mi=0The distance from a vertex v to a vertex u in G, denoted d(v, u), is the length of a minimum length path(also called shortest path) from v to u, if such a path exists. Dijkstra's algorithm applies a greedy methodpattern to the single-source shortest-path problem performing a "weighted" BFS starting at a vertex v. Inthis question you are asked to implement the Dijkstra's algorithm on a weighted graph using adjacencylist structure.

C++ code :- #include<iostream> #include<stdio.h> using namespace std; #define INFINITY…

Answered: Hello, I have this Dijkstra’s exercise.…

Engineering

Computer Science

Hello, I have this Dijkstra’s exercise. could you help me to solve it? In C# and C++

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

2. Let G = (V, E) be a directed weighted graph with the vertices V = {A, B, C, D, E, F) and the edges E= {(A, B, 12), (A, D, 17), (B, C, 8), (B, D, 13), (B, E, 15), (B, F, 13), (C, E, 12), (C, F, 25)}, where the third components is the cost. (a) Write down the adjacency list representation the graph G = (V, E).
Given a graph that is a tree (connected and acyclic). (I) Pick any vertex v.(II) Compute the shortest path from v to every other vertex. Let w be the vertex with the largest shortest path distance.(III) Compute the shortest path from w to every other vertex. Let x be the vertex with the largest shortest path distance. Consider the path p from w to x. Which of the following are truea. p is the longest path in the graphb. p is the shortest path in the graphc. p can be calculated in time linear in the number of edges/vertices
Given a graph that is a tree (connected and acyclic). (1) Pick any vertex v. (II) Compute the shortest path from v to every other vertex. Let w be the vertex with the largest shortest path distance. (III) Compute the shortest path from w to every other vertex. Let x be the vertex with the largest shortest path distance. Consider the path p from w to x. Which of the following are true a. p is the longest path in the graph b. p is the shortest path in the graph c. p can be calculated in time linear in the number of edges/vertices a,c a,b a,b,c b.c
4. Let G=(V, E) be the following undirected graph: V = {1, 2, 3, 4, 5, 6, 7, 8} E = {(1, 7) (1, 4), (1, 6), (6, 4), (7, 5), (2, 5), (2, 4), (4, 3), (4, 8), (8, 3), (3, 5)}. a. Draw G. b. Is G connected? c. Give the adjacency matrix for the graph G given above. d. Determine whether the graph has a Hamiltonian cycle. If the graph does have a Hamiltonian cycle, specify the nodes of one. If it does not, prove that it does not have one. e. Determine whether the graph has a Euler cycle. If the graph does have a Euler cycle, specify the nodes of one. If it does not, prove that it does not have one.
You are given a bipartite graph G=(U,V,E), and an integer K. U and V are the two bipartitions of the graph such that |U| = |V| = N , and E is the edge set. The vertices of U are {1,2,...,N } and that of V are {N+1,N+2,...,2N }. You need to find out whether the total number of different perfect matchings in G is strictly greater than K or not. Recall that a perfect matching is a subset of E such that every vertex of the graph belongs to exactly one edge in the subset. Two perfect matchings are considered to be different even if one edge is different. Write a program in C++ programming language that prints a single line containing “Perfect” if the number of perfect matchings is greater than K, and “Not perfect” in other cases.Sample Input:3 5 21 42 62 53 53 5Output:Not Perfect
5. (This question goes slightly beyond what was covered in the lectures, but you can solve it by combining algorithms that we have described.) A directed graph is said to be strongly connected if every vertex is reachable from every other vertex; i.e., for every pair of vertices u, v, there is a directed path from u to v and a directed path from v to u. A strong component of a graph is then a maximal subgraph that is strongly connected. That is all vertices in a strong component can reach each other, and any other vertex in the directed graph either cannot reach the strong component or cannot be reached from the component. (Note that we are considering directed graphs, so for a pair of vertices u and v there could be a path from u to v, but no path path from v back to u; in that case, u and v are not in the same strong component, even though they are connected by a path in one direction.) Given a vertex v in a directed graph D, design an algorithm for com- puting the strong connected…
Given the following undirected unweighted graph G(V, E). a C What is E? b d e
In Computer Science a Graph is represented using an adjacency matrix. Ismatrix is a square matrix whose dimension is the total number of vertices.The following example shows the graphical representation of a graph with 5 vertices, its matrixof adjacency, degree of entry and exit of each vertex, that is, the total number ofarrows that enter or leave each vertex (verify in the image) and the loops of the graph, that issay the vertices that connect with themselvesTo program it, use Object Oriented Programming concepts (Classes, objects, attributes, methods), it can be in Java or in Python.-Declare a constant V with value 5-Declare a variable called Graph that is a VxV matrix of integers-Define a MENU procedure with the following textGRAPHS1. Create Graph2.Show Graph3. Adjacency between pairs4.Input degree5.Output degree6.Loops0.exit-Validate MENU so that it receives only valid options (from 0 to 6), otherwise send an error message and repeat the reading-Make the MENU call in the main…
Given N cities represented as vertices V₁, V2, un on an undirected graph (i.e., each edge can be traversed in both directions). The graph is fully-connected where the edge eij connecting any two vertices vį and vj is the straight-line distance between these two cities. We want to search for the shortest path from v₁ (the source) to VN (the destination). ... Assume that all edges have different values, and €₁,7 has the largest value among the edges. That is, the source and destination have the largest straight-line distance. Compare the lists of explored vertices when we run the uniform-cost search and the A* search for this problem. Hint: The straight-line distance is the shortest path between any two cities. If you do not know how to start, try to run the algorithms by hand on some small cases first; but remember to make sure your graphs satisfy the conditions in the question.
Consider a weighted, directed graph G with n vertices and m edges that have integer weights. A graph walk is a sequence of not-necessarily-distinct vertices v1, v2, ... , Vk such that each pair of consecutive vertices Vi, Vi+1 are connected by an edge. This is similar to a path, except a walk can have repeated vertices and edges. The length of a walk in a weighted graph is the sum of the weights of the edges in the walk. Let s, t be given vertices in the graph, and L be a positive integer. We are interested counting the number of walks from s to t of length exactly L. Assume all the edge weights are positive. Describe an algorithm that computes the number of graph walks from s to t of length exactly L in O((n+ m)L) time. Prove the correctness and analyze the running time. (Hint: Dynamic Programming solution)
3) The graph k-coloring problem is stated as follows: Given an undirected graph G= (V,E) with N vertices and M edges and an integer k. Assign to each vertex v in V a color c(v) such that 1
(V, E) be a connected, undirected graph. Let A = V, B = V, and f(u) = neighbours of u. Select all that are true. Let G = a) f: AB is not a function Ob) f: A B is a function but we cannot always apply the Pigeonhole Principle with this A, B Odf: A B is a function but we cannot always apply the extended Pigeonhole Principle with this A, B d) none of the above