// A C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
// Number of vertices in the graph
#define V 4
// 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[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// A utility function to print the constructed distance array
int printSolution(int dist[], int n)
{
printf("Vertex Distance from Source\n"); for (int i = 0; i < V; i++)
printf("%d tt %d\n", i
, dist
[i
]); }
// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i
bool sptSet[V]; // sptSet[i] will 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
for (int count = 0; count < V; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int u = minDistance(dist, sptSet);
printf("\n current Node: %d",u
); // Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u]+graph[u][v] < dist[v])
{
dist[v] = dist[u] + graph[u][v];
}
}
// print the constructed distance array
printSolution(dist, V);
}
// driver program to test above function
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = {{0, 4, 1, 0},
{0, 0, 0, -3},
{0, 0, 0, 2},
{0, 0, 0, 0}};
dijkstra(graph, 0);
return 0;
}
Ly8gQSBDKysgcHJvZ3JhbSBmb3IgRGlqa3N0cmEncyBzaW5nbGUgc291cmNlIHNob3J0ZXN0IHBhdGggYWxnb3JpdGhtLgovLyBUaGUgcHJvZ3JhbSBpcyBmb3IgYWRqYWNlbmN5IG1hdHJpeCByZXByZXNlbnRhdGlvbiBvZiB0aGUgZ3JhcGgKCiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8bGltaXRzLmg+CiNpbmNsdWRlIDxzdGRib29sLmg+CgovLyBOdW1iZXIgb2YgdmVydGljZXMgaW4gdGhlIGdyYXBoCiNkZWZpbmUgViA0CgovLyBBIHV0aWxpdHkgZnVuY3Rpb24gdG8gZmluZCB0aGUgdmVydGV4IHdpdGggbWluaW11bSBkaXN0YW5jZSB2YWx1ZSwgZnJvbQovLyB0aGUgc2V0IG9mIHZlcnRpY2VzIG5vdCB5ZXQgaW5jbHVkZWQgaW4gc2hvcnRlc3QgcGF0aCB0cmVlCmludCBtaW5EaXN0YW5jZShpbnQgZGlzdFtdLCBib29sIHNwdFNldFtdKQp7Ci8vIEluaXRpYWxpemUgbWluIHZhbHVlCmludCBtaW4gPSBJTlRfTUFYLCBtaW5faW5kZXg7Cgpmb3IgKGludCB2ID0gMDsgdiA8IFY7IHYrKykKCWlmIChzcHRTZXRbdl0gPT0gZmFsc2UgJiYgZGlzdFt2XSA8PSBtaW4pCgkJbWluID0gZGlzdFt2XSwgbWluX2luZGV4ID0gdjsKCnJldHVybiBtaW5faW5kZXg7Cn0KCi8vIEEgdXRpbGl0eSBmdW5jdGlvbiB0byBwcmludCB0aGUgY29uc3RydWN0ZWQgZGlzdGFuY2UgYXJyYXkKaW50IHByaW50U29sdXRpb24oaW50IGRpc3RbXSwgaW50IG4pCnsKcHJpbnRmKCJWZXJ0ZXggRGlzdGFuY2UgZnJvbSBTb3VyY2VcbiIpOwpmb3IgKGludCBpID0gMDsgaSA8IFY7IGkrKykKCXByaW50ZigiJWQgdHQgJWRcbiIsIGksIGRpc3RbaV0pOwp9CgovLyBGdW50aW9uIHRoYXQgaW1wbGVtZW50cyBEaWprc3RyYSdzIHNpbmdsZSBzb3VyY2Ugc2hvcnRlc3QgcGF0aCBhbGdvcml0aG0KLy8gZm9yIGEgZ3JhcGggcmVwcmVzZW50ZWQgdXNpbmcgYWRqYWNlbmN5IG1hdHJpeCByZXByZXNlbnRhdGlvbgp2b2lkIGRpamtzdHJhKGludCBncmFwaFtWXVtWXSwgaW50IHNyYykKewoJaW50IGRpc3RbVl07CSAvLyBUaGUgb3V0cHV0IGFycmF5LiBkaXN0W2ldIHdpbGwgaG9sZCB0aGUgc2hvcnRlc3QKCQkJCQkvLyBkaXN0YW5jZSBmcm9tIHNyYyB0byBpCgoJYm9vbCBzcHRTZXRbVl07IC8vIHNwdFNldFtpXSB3aWxsIHRydWUgaWYgdmVydGV4IGkgaXMgaW5jbHVkZWQgaW4gc2hvcnRlc3QKCQkJCQkvLyBwYXRoIHRyZWUgb3Igc2hvcnRlc3QgZGlzdGFuY2UgZnJvbSBzcmMgdG8gaSBpcyBmaW5hbGl6ZWQKCgkvLyBJbml0aWFsaXplIGFsbCBkaXN0YW5jZXMgYXMgSU5GSU5JVEUgYW5kIHN0cFNldFtdIGFzIGZhbHNlCglmb3IgKGludCBpID0gMDsgaSA8IFY7IGkrKykKCQlkaXN0W2ldID0gSU5UX01BWCwgc3B0U2V0W2ldID0gZmFsc2U7CgoJLy8gRGlzdGFuY2Ugb2Ygc291cmNlIHZlcnRleCBmcm9tIGl0c2VsZiBpcyBhbHdheXMgMAoJZGlzdFtzcmNdID0gMDsKCgkvLyBGaW5kIHNob3J0ZXN0IHBhdGggZm9yIGFsbCB2ZXJ0aWNlcwoJZm9yIChpbnQgY291bnQgPSAwOyBjb3VudCA8IFY7IGNvdW50KyspCgl7CgkvLyBQaWNrIHRoZSBtaW5pbXVtIGRpc3RhbmNlIHZlcnRleCBmcm9tIHRoZSBzZXQgb2YgdmVydGljZXMgbm90CgkvLyB5ZXQgcHJvY2Vzc2VkLiB1IGlzIGFsd2F5cyBlcXVhbCB0byBzcmMgaW4gZmlyc3QgaXRlcmF0aW9uLgoJaW50IHUgPSBtaW5EaXN0YW5jZShkaXN0LCBzcHRTZXQpOwogICAgcHJpbnRmKCJcbiBjdXJyZW50IE5vZGU6ICVkIix1KTsKCS8vIE1hcmsgdGhlIHBpY2tlZCB2ZXJ0ZXggYXMgcHJvY2Vzc2VkCglzcHRTZXRbdV0gPSB0cnVlOwoKCS8vIFVwZGF0ZSBkaXN0IHZhbHVlIG9mIHRoZSBhZGphY2VudCB2ZXJ0aWNlcyBvZiB0aGUgcGlja2VkIHZlcnRleC4KCWZvciAoaW50IHYgPSAwOyB2IDwgVjsgdisrKQoKCQkvLyBVcGRhdGUgZGlzdFt2XSBvbmx5IGlmIGlzIG5vdCBpbiBzcHRTZXQsIHRoZXJlIGlzIGFuIGVkZ2UgZnJvbQoJCS8vIHUgdG8gdiwgYW5kIHRvdGFsIHdlaWdodCBvZiBwYXRoIGZyb20gc3JjIHRvIHYgdGhyb3VnaCB1IGlzCgkJLy8gc21hbGxlciB0aGFuIGN1cnJlbnQgdmFsdWUgb2YgZGlzdFt2XQoJCWlmICghc3B0U2V0W3ZdICYmIGdyYXBoW3VdW3ZdICYmIGRpc3RbdV0gIT0gSU5UX01BWAoJCQkJCQkJCQkmJiBkaXN0W3VdK2dyYXBoW3VdW3ZdIDwgZGlzdFt2XSkKCQl7CgkJCWRpc3Rbdl0gPSBkaXN0W3VdICsgZ3JhcGhbdV1bdl07CgkJfQoJfQoKCS8vIHByaW50IHRoZSBjb25zdHJ1Y3RlZCBkaXN0YW5jZSBhcnJheQoJcHJpbnRTb2x1dGlvbihkaXN0LCBWKTsKfQoKLy8gZHJpdmVyIHByb2dyYW0gdG8gdGVzdCBhYm92ZSBmdW5jdGlvbgppbnQgbWFpbigpCnsKLyogTGV0IHVzIGNyZWF0ZSB0aGUgZXhhbXBsZSBncmFwaCBkaXNjdXNzZWQgYWJvdmUgKi8KaW50IGdyYXBoW1ZdW1ZdID0ge3swLCA0LCAxLCAwfSwKCQkJCQl7MCwgMCwgMCwgLTN9LAoJCQkJCXswLCAwLCAwLCAyfSwKCQkJCQl7MCwgMCwgMCwgMH19OwoKCWRpamtzdHJhKGdyYXBoLCAwKTsKCglyZXR1cm4gMDsKfQo=