Please implement Dijkstra's algorithms by C++ code to solve the shortest path problem in the given graph.
Graph rules :
The graph is an undirected graph, containing at most 10 nodes named 0 ~ 9.
There is just one edge between two nodes.
The weight of all edges is under 100.
Fill in the blanks marked "//TODO"
Template:
// A C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph
#include <iostream>
using namespace std;
#include <limits.h>
#include <cstring>
// V is the number of vertices in the graph and is initialized to 0
int V = 0;
// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
//TODO
return min_index;
}
// A utility function to print the constructed distance array
void printSolution(int dist[])
{
for (int i = 0; i < V; i++)
cout << i << " "<<dist[i]<< endl;
}
// Function that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int** graph, int src)
{
/*Set the "graphmatrix" 2D array to the adjacency matrix of the graph to use Dijkstra's algorithm
, and the subsequent operations are to use the "graphmatrix" 2D array as the adjacency matrix of the graph to use Dijkstra's algorithm*/
int graphmatrix[V][V];
for(int i = 0;i < V; i++)
for (int j = 0;j < V;j++)
graphmatrix[i][j] = *((int *)graph + i*V + j);
/* "graphmatrix" 2D array is the adjacency matrix of the graph to be processed, while src is the source vertex when using Dijkstra's algorithm. */
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i
bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
//TODO
// print the constructed distance array
printSolution(dist);
}
// driver program to test above function
int main()
{
string cmd;
int E;
cin >> cmd;
//You should create the graph first
if (cmd == "creategraph"){
cin >> V;
cin >> E;
}
//Create the adjacent matrix of the given graph and set it to zero
int graph[V][V];
for (int i = 0; i< V;i++)
for (int j = 0;j < V ; j++ )
graph[i][j] = 1000000;//1000000 is used to represent infinity, which is much larger than the value of all the given edges in the testcase.
while(cin >> cmd){
if(cmd == "addEdge"){
int u;
int v;
int w;
cin >> u;
cin >> v;
cin >> w;
graph[u][v] = w,graph[v][u] = w;
}else if(cmd == "dijkstra"){
int s;//source node
cin >> s;
dijkstra((int**)graph,s);
}else if(cmd == "exit"){
return 0;
}
}
return 0;
}
// This code is contributed by shivanisinghss2110
Hint :
1.The edges in the graph will not have negative values
2.Assume that all input parameters would be valid.
3. Implement the functions below:
minDistance() : A utility function to find the vertex with minimum distance value, from the set of vertices not yet included in shortest path tree
dijkstra() : Function that implements Dijkstra's single source shortest path algorithm for a graph represented using adjacency matrix representation
4.You can use STL.
5.The final calculated shortest path result should be output to the array used to store the shortest path value from the source vertex to each vertex (dist[] in the dijkstra function)
6.Pass the dist[] array with the final result described in 5. to the printSolution function to output the answer in the correct format
7.You don’t have to use the template code, as long as you can find the shortest path value from the source vertex to other vertices in the graph.
8.The same edge will not be input repeatedly (for example, (1,2) and (2,1) or (1,2) and (1,2) will not be input at the same time)
9.The adjacency matrix of the graph to be processed in the dijkstra function is graphmatrix[] and source vertex is src.
10.We assume that when the vertex and the vertex in the adjacent matrix have no edges , 1000000 is used to represent infinity, which is much larger than the value of all the given edges in the testcase.
There are multiple lines in the input.
According to the different instructions, operating the different tasks.
Input format:
First,you will have to create a graph with vertex and edge numbers of this graph as parameters
1.creategraph x y: create a graph with x as numbers of vertex, y as numbers of edge of this graph
Second, you will have several lines to tell you which two nodes are connected and the weight of the edge between the two nodes, the format is below.
The red part is node No.1.(The first parameter after addedge command)
The green part is node No.2.(The second parameter after addedge command)
The blue part is the weight of the edge between node 1 and 2.(The third parameter after addedge command)
Note : There is one graph in one test case.
3.dijkstra x:
Using this command will output the shortest path according to the selected source vertex(Input parameter x) and the given graph.
When you get "dijkstra", you need to print out the shortest path according to the selected source vertex and the given graph.(The output format is shown in sample output)
Suppose there are four vertices from vertex 0 to vertex 3. After using the dijkstra’s algorithm with vertex 0 as the source vertex, the distances from vertex 0 to vertex 1,2 and 3 are calculated to be 8, 6 and 3 respectively. The output format is as follows :
(vertex) (shortest distance from the source vertex to this vertex)
0 0
1 8
2 6
3 3
You can see printSolution() to understand the output format.