In C: Write a program to the shortest exit route from each room to the outside.
ID: 3694964 • Letter: I
Question
In C:
Write a program to the shortest exit route from each room to the outside. You are given a floorplan that shows the rooms and the doors between rooms and between rooms and outside. 1 always denotes the outside. you can model the floorplan as a graph. Each room is a node of the graph and there is an edge between two rooms if there is a door that connects the rooms. Outside area is also considered a room. Graph corresponding to above floorplan is given below. Write a program that reads a file representing a floorplan and outputs the shortest route from each room to outside. Shortest route is the route that has fewest number of doors from the room to the outside. File format is as follows First line of the file contains the number of vertices and number of edges. Each edge is listed on one line with source vertex and destination vertex. Vertices start at 1. Edges are undirected and will be listed on the file once starting with the smallest vertex id. For example, for edges 2-5 and 5-2 the file will only have 2-5. But, you need to insert both to your adjacency list representation. File for above graph is as follows Sample output for above graph should be as follows Shortest paths to outside Use adjacency list representation to store the graph and test your program with different input files. Test your program with different files.Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
// A structure to represent an adjacency list node
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};
// A structure to represent an adjacency list
struct AdjList
{
struct AdjListNode *head; // pointer to head node of list
};
// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
int V;
struct AdjList* array;
};
// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of array will be V
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{
// Add an edge from src to dest. A new node is added to the adjacency
// list of src. The node is added at the begining
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// Since graph is undirected, add an edge from dest to src also
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v)
{
struct AdjListNode* pCrawl = graph->array[v].head;
printf(" Adjacency list of vertex %d head ", v);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf(" ");
}
}
void shortestpath(struct Graph* graph,int n)
{
int flag[10],i=0,counter=2,shortnode[10],v;
struct Graph* regraph = createGraph(n);
for(i=2;i<n;i++)
flag[i]=0;
flag[1]=1;
flag[0]=1;
for(v=2;v<n;v++)
{
struct AdjListNode* pCrawl = graph->array[v].head;
while (pCrawl)
{
if(pCrawl->dest==1)
{
addEdge(regraph, v, 1);
flag[v]=1;
shortnode[counter-2]=v;
counter++;
break;
}
pCrawl = pCrawl->next;
}
}
while(counter!=n)
{
for(i=2;i<n;i++)
{
if(flag[i]==0)
{
for(v=0;v<counter-2;v++)
{
struct AdjListNode* pCrawl = graph->array[i].head;
printf(" Adjacency list of vertex %d head ", v);
while (pCrawl)
{
if(pCrawl->dest==shortnode[v])
{
addEdge(regraph, i, pCrawl->dest);
struct AdjListNode* repCrawl = regraph->array[i].head;
while(repCrawl)
{
addEdge(regraph, i,repCrawl->dest );
repCrawl=repCrawl->next;
}
flag[i]=1;
shortnode[counter-2]=v;
counter++;
break;
}
pCrawl=pCrawl->next;
}
}
}
}
}
printGraph(regraph);
}
// Driver program to test above functions
int main()
{
// create the graph given in above fugure
int V=6,E,i,src,dest;
struct Graph* graph;
FILE *myFile;
myFile = fopen("somenumbers.txt", "r");
fscanf(myFile, "%d %d", V,E);
graph = createGraph(V+1);
for(i=0;i<E;i++)
{
fscanf(myFile, "%d %d", src,dest);
addEdge(graph, src, dest);
}
shortestpath(graph,V+1);
return 0;
}