Kuskal and Dijkstra

Question

bsdpowa 0 Newbie Poster

17 Years Ago

Can anyone help me with Kuskal and Dijkstra algorithms in C#? I have no idea where to start. Any tips?

.net:c# algorithm-pseudocode

3 Contributors
9 Replies
132 Views
3 Days Discussion Span
Latest Post 17 Years Ago Latest Post by Ramy Mahrous

Dani AI

Generated 9 Months Ago

The example posted by is a useful student implementation, but it mixes several approaches (Prim-style heap code alongside MST logic), which is exactly the point flagged. Quick orientation: Kruskal builds a minimum spanning tree by sorting edges and using a disjoint‑set (union‑find) to avoid cycles; Dijkstra finds single‑source shortest paths for nonnegative weights and relies on a min‑priority queue. Background reading: Kruskal (https://en.wikipedia.org/wiki/Kruskal%27s_algorithm), Dijkstra (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), disjoint set (https://en.wikipedia.org/wiki/Disjoint-set_data_structure).

For Kruskal in C#: collect edges in a List<Edge> and sort by weight, then run a UnionFind with path compression and union by rank to test whether an edge joins two different components. Minimal UnionFind example:

class UnionFind {
  int[] parent, rank;
  public UnionFind(int n) { parent = new int[n]; rank = new int[n]; for (int i=0;i<n;i++) parent[i]=i; }
  public int Find(int x) { if (parent[x]!=x) parent[x]=Find(parent[x]); return parent[x]; }
  public void Union(int a,int b) { a=Find(a); b=Find(b); if (a==b) return; if (rank[a]<rank[b]) parent[a]=b; else if (rank[b]<rank[a]) parent[b]=a; else { parent[b]=a; rank[a]++; } }
}

For Dijkstra in modern .NET use adjacency lists and PriorityQueue<TElement,TPriority> (see docs). Push (vertex,dist) pairs and ignore stale entries when dequeued:

var pq = new PriorityQueue<int,int>();
dist[src]=0; pq.Enqueue(src,0);
while (pq.Count>0) {
  pq.TryDequeue(out int u, out int d);
  if (d!=dist[u]) continue;
  foreach (var (v,w) in adj[u]) if (d+w < dist[v]) { dist[v]=d+w; pq.Enqueue(v,dist[v]); }
}

Practical tips: avoid adjacency matrices for large graphs (memory/time), use long for large path sums, map char labels to indices via Dictionary<char,int>, and remember Dijkstra requires nonnegative weights (use Bellman‑Ford for negatives). Kruskal does not need a heap; Prim and Dijkstra do. Unit‑test on small graphs and watch for stale entries in heap-based implementations.

All 9 Replies

Ramy Mahrous 401 Postaholic

17 Years Ago

My team and I developed those two algorithms in C#, when I back home I'll attach you the source code. Please remind me after 8 hrs from now.

Ramy Mahrous 401 Postaholic

17 Years Ago

Never mind, I understood you :)

thoughtcoder 167 Junior Poster

17 Years Ago

You're just going to give the code? What?

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

bsdpowa 0 Newbie Poster · Answer 1 · 2009-04-14T20:05:55+00:00

Thank you very much, I will remind you later.

P.S. If there's any mod available I would be thankful if he/she could rename Kuskal to Kruskal. Typo.

Ramy Mahrous 401 Postaholic Featured Poster · Answer 2 · 2009-04-16T04:27:28+00:00

Kruskal code

void swap ( ref Node a, ref Node b )
		{
			///<Rizk>
			Node c = a ;
			a = b ;
			b = c ;
			///</Rizk>
		}

		/// <summary>
		/// Calculate the Left Child node of a Parent
		/// Used in Heap
		/// </summary>
		/// <param name="i"></param>
		/// <returns></returns>
		int left ( int i )
		{
			///<Rizk>
			return i * 2;
			///</Rizk>
		}

		//Calculate the right Child node of a Parent
		//Used in Heap

		int right ( int i )
		{
			///<Rizk>
			return i * 2 + 1;
			///</Rizk>
		}

		// Arrange the Heap to Exatract the Minimum

		void Min_Heapify ( Node [] a, int i, int Heap_Size )
		{
			///<Rizk>
			int min;
			int l = left ( i );
			int r = right ( i );

			if ( l <= Heap_Size &&  a[ l - 1 ].key < a [ i - 1 ].key )
				min = l;
			else
				min = i;

			if ( r <= Heap_Size && a[ r - 1 ].key < a [ min - 1 ].key )
				min = r;

			if ( min != i )
			{
				swap ( ref a [ i - 1 ], ref a [ min - 1 ] );
				Min_Heapify ( a , min , Heap_Size );
			}
			///</Rizk>
		}

		// Bulid the Heap

		void Build_Min_Heap ( Node [] a, int Heap_Size )
		{
			///<Rizk>
			for ( int i = a.Length/2; i >= 1; i--)
				Min_Heapify ( a , i , Heap_Size );
			///</Rizk>
		}

		//Extract the Minimum Node

		Node Extract_Min ( Node [] a, int Heap_Size )
		{
			///<Rizk>
			Build_Min_Heap ( a , Heap_Size );
			return a [ 0 ];
			///</Rizk>
		}

		//Linear Search to Allow the Coder to Specify the subscriptor by Char
		//rether than by int Value
		// Used by Prim's Algorithm...

		int searchForName ( char name , char [] array )
		{
			///<Rizk>
			for ( int i = 0; i < array.Length; i++ )
				if ( name == array[ i ] )
					return i;
			return -1;
			///</Rizk>
		}

		int searchForName ( char name , Node [] array )
		{
			///<Rizk>
			for ( int i = 0; i < array.Length; i++ )
				if ( name == array[ i ].to )
					return i;
			return -1;
			///</Rizk>
		}

		void intialize_nodes ( char [] alternatives, char r )   
		{
			///<Rizk>
			ArrayOfNodes = new Node [ alternatives.Length ];

			for ( int i = 0; i < alternatives.Length; i++ )
			{
				ArrayOfNodes[ i ].to = alternatives [ i ];
				ArrayOfNodes[ i ].from = Const_char;
				ArrayOfNodes[ i ].key = Const;
			}

			ArrayOfNodes [ searchForName ( r , ArrayOfNodes ) ].key = 0;
			ArrayOfNodes [ searchForName ( r , ArrayOfNodes ) ].from = '0';
			///</Rizk>
		}   

		void neighbour ( char a , int Heap_Size )
		{
			///<Rizk>
			int size = 0 ;

			for ( int i = 0; i < array_length ; i++ )
				if ( Adjecency_Matrix[ searchForName ( a , alternatives ) , i ] > 0  &&  IsFoundInHeap ( a , Heap_Size ) )
					size ++;

			Array_Of_Related_Nodes = new char [ size ];

			for ( int i = 0, z = 0; i < array_length; i++ )
				if ( Adjecency_Matrix[ searchForName ( a , alternatives ) , i ] > 0 && IsFoundInHeap ( a , Heap_Size ) )
				{
					Array_Of_Related_Nodes [ z++ ] = alternatives [ i ] ;
					
					if ( ArrayOfNodes [ searchForName ( alternatives [ i ] , ArrayOfNodes ) ].from == Const_char )
						ArrayOfNodes [ searchForName ( alternatives [ i ] , ArrayOfNodes ) ].from = a ;
				}
			///</Rizk>
		}

		bool IsFoundInHeap ( char a , int Heap_Size )
		{
			///<Rizk>
			for ( int i = 0; i < Heap_Size; i++ )
				if ( ArrayOfNodes [ i ].to == a )
					return true;
			return false;
			///</Rizk>
		}

		void MST_Prime_Algorithm ( char r, int [ , ] Adjacency_Matrix, char [] alternatives, Node [] arrayOfNodes )
		{
			///<Rizk>
			intialize_nodes ( alternatives , r );
            string ramrom="Ramy.wav";
			int Heap_Size = array_length;
			Node q;
			int z = 0;
			while ( Heap_Size > 0 )
			{
				q = Extract_Min ( ArrayOfNodes , Heap_Size );
				neighbour ( q.to , Heap_Size );

				for ( int ii = 0; ii < Array_Of_Related_Nodes.Length; ii++ )
				{
					//check if the weight between the two vertex is less that or larger than the weight at the heap
					if ( Adjacency_Matrix [ searchForName ( q.to, alternatives ) , searchForName ( Array_Of_Related_Nodes [ ii ] , alternatives ) ] < ArrayOfNodes [ searchForName ( Array_Of_Related_Nodes [ ii ], ArrayOfNodes ) ].key )
					{
						//replace with the minimum weight
						ArrayOfNodes [ searchForName ( Array_Of_Related_Nodes [ ii ] , ArrayOfNodes ) ].key =  Adjacency_Matrix [ searchForName ( q.to, alternatives ) , searchForName ( Array_Of_Related_Nodes [ ii ] , alternatives ) ];
						ArrayOfNodes [ searchForName ( Array_Of_Related_Nodes [ ii ] , ArrayOfNodes ) ].from = q.to;
					}
				}

				array_final [ z ].to = q.to ;
				array_final [ z ].from = q.from;
				array_final [ z ].key = q.key;
				z++ ;
				if ( flagfirst == 0 )
				{
					Thread.Sleep(1000);
					this.DrawAnswerPrim( q.to, q.from, q.key );
					MessageBox.Show ( " Next " ,"Solution",MessageBoxButtons.OK,MessageBoxIcon.Information);
				}
				swap ( ref ArrayOfNodes[ searchForName( q.to , ArrayOfNodes ) ] , ref ArrayOfNodes [ Heap_Size - 1 ] );
				Heap_Size -- ;
				flagfirst = 0;
			}
			///</Rizk>
		}
int Get_smallest_other_Algorithm ( int [ , ] Adjecency_Matrix_Temp, ref int x, ref int y, ref int small )
		{
			///<Rizk>
			int flg = 0 ;
			int col, row;
			for ( col = 0; col < array_length; col++ )
			{
				for ( row=0;row< array_length ; row++ )
					if ( ( Adjecency_Matrix_Temp [ col, row ] != 0 ) && ( col != row ) && ( Adjecency_Matrix_Temp [ col, row ] != 10000 ) )
					{
						small = Adjecency_Matrix_Temp [ col, row ];
						x = col;
						y = row;
						flg = 1;
						break;
					}
				if ( flg == 1 )
					break ;
			}
			
			for ( col = 0; col < array_length; col++ )
			{
				for ( row = 0; row < array_length; row++ )
					if ( ( Adjecency_Matrix_Temp [ col, row ] < small ) && ( Adjecency_Matrix_Temp [ col, row ] != 0 ) 
						&& ( col != row ) && ( Adjecency_Matrix_Temp [ col, row ] != 10000 ) )
					{
						small = Adjecency_Matrix_Temp [ col, row ];
						x = col;
						y = row;
					}
			}
			return 0 ;
			///</Rizk>
		}


		int  MST_other_Algorithm ( int small,int [ , ] Adjecency_Matrix_Temp, ref int  a, ref int  b)
		{
			///<Rizk>
			int check = 0;
			if ( ( Adjecency_Matrix_Temp [ a , a ] == 0 ) && ( Adjecency_Matrix_Temp [ b , b ] != 0 ) )
				check = 1;
			if ( ( Adjecency_Matrix_Temp [ a , a ] != 0 ) && ( Adjecency_Matrix_Temp [ b , b ] == 0 ) )
				check = 1;
			if ( ( Adjecency_Matrix_Temp [ a , a ] == 0 ) && ( Adjecency_Matrix_Temp [ b , b ] == 0 ) )
				check = 1;
			if ( check == 1 )
			{
				
				len++;
				array_final [ len ].to = alternatives [ a ];
				array_final [ len ].from = alternatives [ b ];
				array_final [ len ].key= Adjecency_Matrix [ a, b ];
				///
				this.DrawAnswerKrusk( alternatives [ a ], alternatives [ b ], Adjecency_Matrix[a,b] );
				///
				MessageBox.Show ( " Next " ,"Solution",MessageBoxButtons.OK,MessageBoxIcon.Information);
				Adjecency_Matrix_Temp[a,b]= 10000;
				Adjecency_Matrix_Temp[b,a]= 10000;
				Adjecency_Matrix_Temp[a,a]= 1;
				Adjecency_Matrix_Temp[b,b]= 1;
				
			}
			else 
			{
				Adjecency_Matrix_Temp[a,b]= 0;
				Adjecency_Matrix_Temp[b,a]= 0;
			}
			return 0;
			///</Rizk>
		}

		int  check_end_other_Algorithm ( int [ , ] Adjecency_Matrix_Temp )
		{
			///<Rizk>
			int x ,y ;

			for ( x = 0; x < array_length; x ++ )
			{
				for ( y = 0; y < array_length ; y ++ )
				{
					if ( ( Adjecency_Matrix_Temp [ x , y ] == 0 ) && ( x == y ) )
						return 0;
				}
			}
		
			return 1 ;
			///</Rizk>
		}

This code we developed 4 years ago, I don't expect any beneficial unless you know the algorithm well.

bsdpowa 0 Newbie Poster · Answer 3 · 2009-04-17T19:52:17+00:00

bsdpowa 0 Newbie Poster

17 Years Ago

Thank you very much Ramy!

Ramy Mahrous 401 Postaholic Featured Poster · Answer 4 · 2009-04-17T23:56:35+00:00

Ramy Mahrous 401 Postaholic

17 Years Ago

Please mark this thread as solved :)

thoughtcoder 167 Junior Poster · Answer 5 · 2009-04-18T06:57:56+00:00

Agh why is there priority queue code mixed in? Kill me now.

Ramy Mahrous 401 Postaholic Featured Poster · Answer 6 · 2009-04-18T09:27:04+00:00

It's not the best, it's what we wrote when I was student, and I didn't work in this algorithm I was in GUI Layer.

Kuskal and Dijkstra

Dani AI

Recommended Answers Collapse Answers

All 9 Replies

Recommended Answers