Write me a C code for an weighted, un-directed graph that performs dijkstra's algorithm on graph along with some basic functions as mentioned in description.
$10-30 USD
Cancelado
Publicado há mais de 5 anos
$10-30 USD
Pago na entrega
Problem Statement
• Input: A directed graph G = (V, E) with weight function w : E → N.
• Goal: Serve the following requests:
– Given u, v ∈ V , what is the weight of edge (u, v)?
– Given v ∈ V , run Dijkstra’s algorithm on G from vertex v.
– Given u, v ∈ V , output shortest path from a vertex u to v.
Input Format
General format:
A graph G = (V, E) is defined by first providing the number of vertices n = |V |.
Henceforth you shall assume that the vertex set is V = {1, 2, . . . , n}.
The edge set E and the weight function w are provided together.
Each neighbour v of a vertex u will be given in the adjacency list of u along with w(u, v).
Requests arrive only after the definition of G.
Format in detail:
Each line of the input looks like one of the following:
• ‘N’ followed by number of vertices n ∈ N.
• ‘E’ followed by a vertex and vertex-weight pairs that look like:
u, v1,w(u, v1), v2,w(u, v2) · · · , vk,w(u, vk)
This list gives the adjacency list of vertex u along with the respective edge weights.
The list is given as a space-separated list.
• ‘?’ followed by u, v ∈ [n] with a space separating them.
• ‘D’ followed by a u ∈ [n].
• ‘P’ followed by u, v ∈ [n] with a space separating them.
Each of the lines above ends with a ‘\n’ character. All lists are given as elements separated
by a space. No commas are used anywhere. All numbers used will fit inside an int. End of
input is indicated by EOF.
Output Format
• If input line started with ‘N’ or ‘E’, then no corresponding output.
• If input line was “? u v”: Output w(u, v) if (u, v) ∈ E, −1 otherwise.
• If input line was “D u”:
Let v1, v2, . . . , vn be the order of vertices visited on a run of of Dijkstra’s algorithm
from u (note that u = v1). Let δ(u, v) denote the shortest path from u to v. Output
a list of pairs: (v1, δ(u, v1)), . . . ,(vn, δ(u, vn)). If δ(u, v) = ∞ then output −1 in its
place. Use a space to separate v and δ(u, v) within a pair. Use a ‘\n’ between pairs.
• If input line was “P u v”:
If v is not reachable from u, output −1. Else output the shortest distance from u to
v followed by a shortest path from u to v as a space-separated list of vertices starting
with u.
All output lines have to end with a ‘\n’ character.
Implementation rules
• The input graph G = (V, E) is stored similar to Assignment 4. The edge weights are
stored in an additional variable inside the nodes in the adjacency list (see CLRS).
• Store each vertex’s adjacency list in the same order as provided in the input.
• Dijkstra’s algorithm requires a min-priority queue. Implement a min-priority queue by
using a min-heap.
Hi there, I do algorithms and have done Dijkstra before. I would like to do this project if given the opportunity. Let me know if you are interested so I can have further details.
I have the knowledge required for the project. I have worked on similar projects in the past and can use my experience to make a better application for you
Program consists of:
- string i/o
- data structure(s)
- and the Dijkstra algorithm
None of the above parts are particularly difficult, but the formatting of the input and output is hard to visualize.
I'd appreciate example input(s) and output(s).
Hi,
I have been tutoring computer programming online for the past 3 years.
I have solved over a 1000 assignments in C programming.
I can help you with your problem.
Thanks