Question

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

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

Homework Answers

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;
}

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
JAVA Describe an efficient algorithm that converts the Adjacency list representation of a graph to the...
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...
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...
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...
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...
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...
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...
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.
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...
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....
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...