# 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.

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.

Skills: Algorithm, C Programming, Mathematics

About the Employer:
( 0 reviews ) Hyderabad, India

Project ID: #17965787

## Awarded to:

AhmadBilal891

I will do this...Not for money. only for enjoyment... I m sure you will like to work with me next time...

\$25 USD in 1 day
(0 Reviews)
0.0

## 14 freelancers are bidding on average \$33 for this job

it2051229

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.

\$30 USD in 1 day
(510 Reviews)
7.0
trutony

Hi, I am a talented C & C++ coder. I won the championship 4 times in Codechef. If you give me this project, you will get a good result. Thanks. Relevant skills & experiences: C & C++ Programming, Algorithm, Data proce More

\$100 USD in 1 day
(20 Reviews)
5.2
jboo7

I have a lot of experience in C/C++ and Java also. I can do the job good and fast, also I know algorithms and data structures.

\$25 USD in 1 day
(22 Reviews)
4.2
Nerdulent

hi...by when is it that you need it completed? thanks

\$50 USD in 5 days
(2 Reviews)
2.4
Arnav28aviraj

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

\$20 USD in 3 days
(1 Review)
0.4
yousuf1234567

I can give the best possible dijisktra algorithm. I can help you with this project I have made this project a several time.

\$25 USD in 1 day
(0 Reviews)
0.0
tafseerahmed

I am an expert in c/c++, algorithms and data structures. You can check some of my previous C++ , [login to view URL] -what are your requirements? -what are the deadlines? Message me More

\$30 USD in 1 day
(0 Reviews)
0.0
scrapinghub

##will deliver it within 2 hrs## Hi, I have more than 4+ yr of experience in field of .net and python web scraping and data mining. And worked on many such kind of projects. I have read the details and ready to start More

\$15 USD in 1 day
(0 Reviews)
0.0
MinimalCyan

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 appreciat More

\$40 USD in 5 days
(0 Reviews)
0.0
kanak15140

Hi, I'm quite good with competitive programming and have done a few problems of this kind in past. Looking forward to working with you.

\$20 USD in 1 day
(1 Review)
0.1
bali161616

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

\$35 USD in 2 days
(0 Reviews)
0.0
gar55660fb4204a1

I've done this in my college

\$25 USD in 1 day
(0 Reviews)
0.0
Shashank447

Half of your work is ready with me. Contact me if you want the work to complete in quick. Hope to work with you ASAP.

\$18 USD in 1 day
(0 Reviews)
0.0