Dijkstra Algorithm Implementation in C/C++ - Revision history

Arjun Suresh at 16:41, 22 February 2014

2014-02-22T16:41:58Z

Arjun Suresh: Arjun Suresh moved page Dijkstra Algorithm Implementation in C\C++ to Dijkstra Algorithm Implementation in C/C++

2014-01-28T21:00:49Z

Arjun Suresh moved page Dijkstra Algorithm Implementation in C\C++ to Dijkstra Algorithm Implementation in C/C++

Arjun Suresh at 22:28, 18 December 2013

2013-12-18T22:28:32Z

Arjun Suresh at 21:57, 13 December 2013

2013-12-13T21:57:15Z

Arjun Suresh at 21:42, 13 December 2013

2013-12-13T21:42:30Z

Arjun Suresh at 21:42, 13 December 2013

2013-12-13T21:42:07Z

Arjun Suresh at 21:41, 13 December 2013

2013-12-13T21:41:35Z

Arjun Suresh at 21:41, 13 December 2013

2013-12-13T21:41:18Z

Arjun Suresh: Created page with " #include using namespace std; struct vert { char neighbour[20]; int cost[20]; int nn; char name; int color; in..."

2013-12-13T21:40:46Z

Created page with "<syntaxhighlighter lang="C"> #include<iostream> using namespace std; struct vert { char neighbour[20]; int cost[20]; int nn; char name; int color; in..."

New page

<syntaxhighlighter lang="C">

#include<iostream>
using namespace std;

struct vert
{
char neighbour[20];
int cost[20];
int nn;
char name;
int color;
int d;
char pi;

};

int vi = 0;
vert vertex[20];
int findi(char a)
{
int i;
for(i = 0; i < vi; i++)
if(vertex[i].name == a)
return i;
return 0;
}
void dij(char start);

int main()
{
char b, a,start;
int c, d, i, u, w;

cout<<"Enter the edges and weights\n0 to stop:\n";
while(1)
{
cin >> a;
if(a == '0')
break;
cin >> b;
cin >> w;
c = 0, d = 0;
for(i = 0; i < vi; i++)
{
if(a == vertex[i].name)
{
vertex[i].cost[vertex[i].nn] = w;
vertex[i].neighbour[vertex[i].nn++] = b;
c++;
}
if(b == vertex[i].name)
{
d++;
}
}
if(c == 0)
{
vertex[vi].name = a;
vertex[vi].nn = 0;
vertex[vi].cost[vertex[vi].nn] = w;
vertex[vi++].neighbour[vertex[vi].nn++] = b;
}
if(d == 0)
{
vertex[vi++].name = b;
vertex[vi].nn = 0;
}
}
cout<<"Enter the starting vertex: ";
cin>>start;
dij(start);
cout<<endl;
}

void dij(char start)
{
int i;
int front = 0, u, c = 0;
int queue[50], qi = 0;
int s[50], si = 0, j, d;
for(i = 0; i < vi; i++)
{
if(vertex[i].name == start)
{
vertex[i].d = 0;
vertex[i].pi = 0;
}
else
{
vertex[i].color = 0;
vertex[i].d = 0x7ffffffff;
vertex[i].pi = 0;
}
queue[qi++] = i;
}
while(front < qi)
{
for(i = front; i < qi; i++)
for(j = front; j < qi-i+front-1; j++)
if(vertex[queue[j]].d > vertex[queue[j+1]].d)
{
u = queue[j];
queue[j] = queue[j+1];
queue[j+1] = u;
}
u = queue[front++];
s[si++] = u;
cout << vertex[u].name << endl;
for(i = 0; i < vertex[u].nn; i++)
if(vertex[u].cost[i]+vertex[u].d<vertex[findi(vertex[u].neighbour[i])].d)
{
vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d+vertex[u].cost[i];
vertex[findi(vertex[u].neighbour[i])].pi = u;
}
}
for(i = 0; i < vi; i++)
{
cout << endl << endl << vertex[i].name << "\t" << vertex[vertex[i].pi].name << endl;
}
}

</syntaxhighlighter>

{{Template:FB}}

<disqus/>

[[Category:Graphs]]

@@ Line 1: / Line 1: @@
 <metadesc>Dijkstra Algorithm Implementation in C\C++, Graph Algorithm </metadesc>
-<syntaxhighlight lang="C">
+<syntaxhighlight lang="C" name="dijkstra">
 #include<iostream>

← Older revision		Revision as of 22:28, 18 December 2013
Line 1:		Line 1:
		+	<metadesc>Dijkstra Algorithm Implementation in C\C++, Graph Algorithm </metadesc>
		+
	<syntaxhighlight lang="C">		<syntaxhighlight lang="C">

@@ Line 69: / Line 69: @@
+		}
+	}
-	cout<<"Enter the starting vertex: ";
+	cout << "Enter the starting vertex: ";
-	cin>>start;
+	cin >> start;
 	dij(start);
 	cout << endl;

← Older revision		Revision as of 21:41, 13 December 2013
Line 1:		Line 1:
−	<~~syntaxhighlighter~~ lang="C">	+	<syntaxhighlight lang="C">

	#include<iostream>		#include<iostream>

← Older revision	Revision as of 21:00, 28 January 2014
(No difference)

@@ Line 110: / Line 110: @@
 		cout << vertex[u].name << endl;
 		for(i = 0; i < vertex[u].nn; i++)
-		    if(vertex[u].cost[i]+vertex[u].d<vertex[findi(vertex[u].neighbour[i])].d)
+		    if(vertex[u].cost[i] + vertex[u].d < vertex[findi(vertex[u].neighbour[i])].d)
+		    {
-			vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d+vertex[u].cost[i];
+			vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d + vertex[u].cost[i];
 			vertex[findi(vertex[u].neighbour[i])].pi = u;
+		    }

@@ Line 72: / Line 72: @@
 	cin>>start;
 	dij(start);
-	cout<<endl;
+	cout << endl;
+}
@@ Line 122: / Line 122: @@
+}
-</syntaxhighlighter>
+</syntaxhighlight>

@@ Line 18: / Line 18: @@
 int vi = 0;
 vert vertex[20];
 int findi(char a)
+{