Question

Implement Dijkstra’s Shortest Path Algorithm in C using an Adjacency List (linked list) graph.

Answer #1

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct node_t node_t;

typedef struct edge_t edge_t;

struct edge_t {

node_t *nd; /* target of this edge
*/

edge_t *sibling;/* for singly linked list */

int len; /* edge cost */

};

struct node_t {

edge_t *edge; /* singly linked list of
edges */

node_t *via; /* where previous node is in
shortest path */

double dist; /* distance from the source
*/

char name[8]; /* vertex name */

int heap_idx; /* link to heap position for
updating distance */

};

/*edge*/

#define BLOCK_SIZE 15

edge_t *edge_root = 0, *e_next = 0;

void add_edge(node_t *a, node_t *b, double d)

{

if (e_next == edge_root) {

edge_root =
(edge_t*)malloc(sizeof(edge_t) * (BLOCK_SIZE + 1));

edge_root[BLOCK_SIZE].sibling =
e_next;

e_next = edge_root +
BLOCK_SIZE;

}

--e_next;

e_next->nd = b;

e_next->len = d;

e_next->sibling = a->edge;

a->edge = e_next;

}

void free_edges()

{

for (; edge_root; edge_root = e_next) {

e_next =
edge_root[BLOCK_SIZE].sibling;

free(edge_root);

}

}

/* priority queue */

node_t **heap;

int heap_len;

void set_dist(node_t *nd, node_t *via, double d)

{

int i, j;

/* already knew better path */

if (nd->via && d >= nd->dist)
return;

/* find existing heap entry, or create a new one
*/

nd->dist = d;

nd->via = via;

i = nd->heap_idx;

if (!i) i = ++heap_len;

/* upheap */

for (; i > 1 && nd->dist < heap[j =
i/2]->dist; i = j)

(heap[i] = heap[j])->heap_idx =
i;

heap[i] = nd;

nd->heap_idx = i;

}

node_t * pop_queue()

{

node_t *nd, *tmp;

int i, j;

if (!heap_len) return 0;

/* remove leading element, pull tail element there and
downheap */

nd = heap[1];

tmp = heap[heap_len--];

for (i = 1; i < heap_len && (j = i * 2)
<= heap_len; i = j) {

if (j < heap_len &&
heap[j]->dist > heap[j+1]->dist) j++;

if (heap[j]->dist >=
tmp->dist) break;

(heap[i] = heap[j])->heap_idx =
i;

}

heap[i] = tmp;

tmp->heap_idx = i;

return nd;

}

/* Dijkstra's algorithm; unreachable nodes will never make into the
queue */

void calc_all(node_t *start)

{

node_t *lead;

edge_t *e;

set_dist(start, start, 0);

while ((lead = pop_queue()))

for (e = lead->edge; e; e =
e->sibling)

set_dist(e->nd, lead, lead->dist + e->len);

}

void show_path(node_t *nd)

{

if (nd->via == nd)

printf("%s", nd->name);

else if (!nd->via)

printf("%s(unreached)",
nd->name);

else {

show_path(nd->via);

printf("-> %s(%g) ",
nd->name, nd->dist);

}

}

int main(void)

{

#define N_NODES 6

node_t *nodes = (node_t*)calloc(sizeof(node_t), N_NODES);

for (int i = 0; i < N_NODES; i++)

sprintf(nodes[i].name, "%c", 'a' + i);

add_edge(nodes, nodes+1, 7); //a-b

add_edge(nodes, nodes+2, 9); //a-c

add_edge(nodes, nodes+5, 14); //a-f

add_edge(nodes+1, nodes+2, 10); //b-c

add_edge(nodes+1, nodes+3, 15); //b-d

add_edge(nodes+2, nodes+3, 11); //c-d

add_edge(nodes+2, nodes+5, 2); //c-f

add_edge(nodes+3, nodes+4, 6); //d-e

add_edge(nodes+4, nodes+5, 9); //e-f

heap = (node_t**)calloc(sizeof(node_t), N_NODES + 1);

heap_len = 0;

calc_all(nodes);

for (int i = 0; i < N_NODES; i++) {

show_path(nodes + i);

putchar('\n');

}

//free memories

free_edges();

free(heap);

free(nodes);

return 0;

}

JAVA
Describe an efficient algorithm that converts the Adjacency list
representation of a graph to the Adjacency matrix representation of
the same graph. What is the running time?
1. Use pseudocode.
2. What is the running time?
Example:
Input: The adjacency list
is:
Adj[0] -> 2
Adj[1] -> 2
Adj[2] -> 0 -> 1
Output: arr[][] = [ [0, 0, 1], [0,
0, 1], [1, 1, 0] ]

Use Dijkstra's single-source shortest path algorithm to
calculate the shortest path from vertex 1 (or Root Vertex) to each
vertex of the graph. The Example you are going to implement should
have minimum 10-
Vertices.
Submit the following:
1. Source Code (C++, Python, Java
etc.)
2. Output of the Code
3. Trace diagrams (hand
written) of the implemented Example

true/false
An unweighted path length measures the number of edges in a
graph.
Breadth first search traverses the graph in "layers", beginning
with the closest nodes to the ending location first.
The computer knows about neighbors by checking the graph storage
(such as the adjacency matrix or the adjacency list).
Breadth first traversals use a stack to process nodes.
The weighted path length is the sum of the edge costs on a
path.
Dijkstra's shortest path algorithm can be used...

Usually, Djikstra’s shortest-path algorithm is not used on
graphs with negative-weight edges because it may fail and give us
an incorrect answer. However, sometimes Djikstra’s will give us the
correct answer even if the graph has negative edges.
You are given graph G with at least one negative edge, and a source
s. Write an algorithm that tests whether Djikstra’s algorithm will
give the correct shortest paths from s. If it does, return the
shortest paths. If not, return ‘no.’...

IN JAVA LANGUAGE
Linked List-Based Stack Implementation
Implement Stack using a Linked List
Use the language library LinkedList
Stack methods will call the LinkedList methods
You can use string as the object
Instead of using an array, as the StackLab did, here you will
use a Linked List from your language's library. Implement all the
methods of Stack : push(), pop(), size(), printStackDown(), etc,
using calls to the linked list methods that correspond to the
actions need. In the array...

Analyze the worst-case complexity of the algorithm below when
using an optimized adjacency list to store G.
ComponentCount:
Input: G = (V, E): an undirected graph with n
vertices and m edges
Input: n, m: the order and size of G,
respectively
Output: the number of connected components in
G
Pseudocode:
comp = n
uf = UnionFind(n)
For v in V:
For u in N(v):
If (uf.Find(v) !=
uf.Find(u))
uf.Union(u, v)
comp = comp - 1...

Analyze the worst-case complexity of the algorithm below when
using an optimized adjacency list to store G.
ComponentCount:
Input: G = (V, E): an undirected graph with n
vertices and m edges
Input: n, m: the order and size of G,
respectively
Output: the number of connected components in
G
Pseudocode:
comp = n
uf = UnionFind(n)
For v in V:
For u in N(v):
If (uf.Find(v) !=
uf.Find(u))
uf.Union(u, v)
comp = comp - 1...

Discuss the Dijkstra’s shortest path algorithm in your own words
with a case example.

Briefly distinguish between Arrays and Linked List. Write an
algorithm for each as well as develop computer programs that
implement each of them. Show the results of your output including
your code.

C PROGRAMMING
Doubly Linked List For this program you’ll implement a doubly
linked list of strings. You must base your code on the doubly
linked list implementation given in my Week 8 slides. Change the
code so that instead of an ‘int’ each node stores a string (choose
a suitable size). Each node should also have a next node pointer,
and previous node pointer. Then write functions to implement the
following linked list operations:
• A printList function that prints...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 9 minutes ago

asked 15 minutes ago

asked 38 minutes ago

asked 39 minutes ago

asked 44 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago