Reply to thread

Message

<blockquote data-quote="EKGuest" data-source="post: 28413322" data-attributes="member: 582168">මේ ප්‍රශ්නේ ටිකක් සංකීර්ණ දේකට තියෙන්නේ Hop Count එක හොයන එක. Dijkstra's Algorithm එකට වෙනස්කම් කිහිපයක් කරලා Hop Count එක හොයන්න පුලුවන්. ඒ වෙනස්කම් තමයි:1. Dijkstra's Algorithm එකේදී හොයන්නේ Source Node එකේ සිට graph එකේ අනිත් සියලුම Nodes වලට තියෙන කෙටිම දුර. නමුත් මේ ප්‍රශ්නේදී හොයන්නේ ඕකේ අනිත් පැත්ත. ඒ කියන්නේ දෙන ලද Node එකකට අනිත් සියලුම Nodes වල සිට ඇති Hop Count එක. ඒ නිසා Dijkstra's Algorithm එකේ අදාල තැන් වෙනස් කල යුතුයි.2. Dijkstra's Algorithm එකේදි nodes අතරේ දුර පෙන්වන්න graph එකක් පාවිච්චි කරනවා වගේ මේ ප්‍රශ්නේදී&nbsp; nodes අතරේ කනෙක්ෂන්ස් පෙන්වන්න Directed Graph එකක් පාවිච්චි කරන්න පුලුවන්. උදා: Node 2 සිට Node 3 දක්වා කනෙක්ෂන් එකක් තියෙන නිසා graph[2,3] = 1 යි නමුත් Node 3 සිට Node 2 දක්වා කනෙක්ෂන් එකක් නැති නිසා graph[3,2] = 0 යි.3. Dijkstra's Algorithm එකේ Node 0 පාවිච්චි කරනවා නමුත් මේ ප්‍රශ්නේ Node 0&nbsp; පාවිච්චි කරන්නේ නැති නිසා Dijkstra's Algorithm එකේ අදාල තැන් වෙනස් කල යුතුයි.4. මේ ප්‍රශ්නේ Node එකකට තව Node එකක් ඩිරෙක්ට් කනෙක්ට් වෙනවානම් Hop Count එක 0 යි. අතරමැද Node 1 ක් හරහා කනෙක්ට් වෙනවානම් Hop Count එක 1 යි. අතර මැද Node 2ක් හරහානම් Hop Count එක 2 යි... ඔය විදියට යන්නේ. ඒක නිසා අපිට අවශ්‍ය Hop Count එක ගන්න Dijkstra's Algorithm එක ඇප්ලයි කරලා එන Hop Count එකෙන් එකක් අඩුකල යුතුයි.Hop Count එක හොයාගත්තට පස්සේ කරන්න තියෙන්නේ node value සහ influence factor එකත් එක්ක දිලා තියෙන ෆෝමියුලා එකට ආදේශ කරලා influence value එක calculate කරන එක.[CODE=csharp]using System;internal class Program{&nbsp; &nbsp; const int INFINITY = int.MaxValue;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; static int noOfNodes;&nbsp; &nbsp; static int[,] graph;&nbsp; &nbsp; static int mainNode;&nbsp; &nbsp; static decimal influenceFactor;&nbsp; &nbsp; static decimal[] nodeValues;&nbsp; &nbsp; static int[] hopCounts;&nbsp; &nbsp; static decimal[] influenceValues;&nbsp; &nbsp; static int[] FindHopCounts(int[,] graph, int mainNode)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; int[] hopCounts = new int[noOfNodes + 1];&nbsp; &nbsp; &nbsp; &nbsp; bool[] sptSet = new bool[noOfNodes + 1];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 1; i &lt;= noOfNodes; i++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hopCounts[i] = INFINITY;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sptSet[i] = false;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; hopCounts[mainNode] = 0;&nbsp; &nbsp; &nbsp; &nbsp; for (int count = 1; count &lt;= noOfNodes; count++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int u = MinHopCountNode(hopCounts, sptSet);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sptSet[u] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int v = 1; v &lt;= noOfNodes; v++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (!sptSet[v] &amp;&amp; graph[v, u] != 0 &amp;&amp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hopCounts[u] != INFINITY &amp;&amp; hopCounts[u] + graph[v, u] &lt; hopCounts[v])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hopCounts[v] = hopCounts[u] + graph[v, u];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 1; i &lt;= noOfNodes; i++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i != mainNode &amp;&amp; hopCounts[i] != INFINITY)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hopCounts[i]--;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return hopCounts;&nbsp; &nbsp; }&nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; static int MinHopCountNode(int[] hopCounts,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bool[] sptSet)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; int minValue = INFINITY, minIndex = -1;&nbsp; &nbsp; &nbsp; &nbsp; for (int v = 1; v &lt;= noOfNodes; v++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (sptSet[v] == false &amp;&amp; hopCounts[v] &lt;= minValue)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minValue = hopCounts[v];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minIndex = v;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return minIndex;&nbsp; &nbsp; }&nbsp; &nbsp; static void CalculateInfluenceValues()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; influenceValues = new decimal[noOfNodes + 1];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 1; i &lt;= noOfNodes; i++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i != mainNode)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (hopCounts[i] != INFINITY)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (hopCounts[i] != 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; influenceValues[i] = nodeValues[i] * influenceFactor * (1m / hopCounts[i]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; influenceValues[i] = decimal.MaxValue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; static void ReadInput()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; Console.Write(&quot;Input number of nodes: &quot;);&nbsp; &nbsp; &nbsp; &nbsp; noOfNodes = int.Parse(Console.ReadLine());&nbsp; &nbsp; &nbsp; &nbsp; Console.Write(&quot;Input main node: &quot;);&nbsp; &nbsp; &nbsp; &nbsp; mainNode = int.Parse(Console.ReadLine());&nbsp; &nbsp; &nbsp; &nbsp; Console.Write(&quot;Input value for each node: &quot;);&nbsp; &nbsp; &nbsp; &nbsp; string[] strNodeValues = Console.ReadLine().Split(' ');&nbsp; &nbsp; &nbsp; &nbsp; nodeValues = new decimal[noOfNodes + 1];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 1; i &lt;= noOfNodes; i++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; nodeValues[i] = int.Parse(strNodeValues[i - 1]);&nbsp; &nbsp; &nbsp; &nbsp; Console.Write(&quot;Input influence factor: &quot;);&nbsp; &nbsp; &nbsp; &nbsp; influenceFactor = decimal.Parse(Console.ReadLine());&nbsp; &nbsp; &nbsp; &nbsp; Console.WriteLine(&quot;Input the graph of connected nodes:&quot;);&nbsp; &nbsp; &nbsp; &nbsp; graph = new int[noOfNodes + 1, noOfNodes + 1];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 1; i &lt;= noOfNodes; i++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; string[] s = Console.ReadLine().Split(',');&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = 1; j &lt;= noOfNodes; j++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; graph[i, j] = int.Parse(s[j - 1]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; static void PrintResults(int[] hopCounts, int mainNode)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; Console.WriteLine();&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 1; i &lt;= noOfNodes; i++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i != mainNode)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; string strHopCount = &quot;&quot;;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (hopCounts[i] == INFINITY)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; strHopCount = &quot;No path&quot;;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; strHopCount = hopCounts[i].ToString();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; string strInfluenceValue = &quot;&quot;;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (hopCounts[i] == INFINITY)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; strInfluenceValue = &quot;No path&quot;;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (influenceValues[i] == decimal.MaxValue)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; strInfluenceValue = &quot;Infinity&quot;;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; strInfluenceValue = influenceValues[i].ToString();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Console.WriteLine(&quot;Hop Count from {0} to {1}: {2}\t\tInfluence value from {3} to {4}: {5}&quot;,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i, mainNode, strHopCount, i, mainNode, strInfluenceValue);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; static void Main(string[] args)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; ReadInput();&nbsp; &nbsp; &nbsp; &nbsp; hopCounts = FindHopCounts(graph, mainNode);&nbsp; &nbsp; &nbsp; &nbsp; CalculateInfluenceValues();&nbsp; &nbsp; &nbsp; &nbsp; PrintResults(hopCounts, mainNode);&nbsp; &nbsp; &nbsp; &nbsp; Console.ReadLine();&nbsp; &nbsp; }}[/CODE][ATTACH=full]191454[/ATTACH][ATTACH=full]191455[/ATTACH]</blockquote>

[QUOTE="EKGuest, post: 28413322, member: 582168"] මේ ප්‍රශ්නේ ටිකක් සංකීර්ණ දේකට තියෙන්නේ Hop Count එක හොයන එක. Dijkstra's Algorithm එකට වෙනස්කම් කිහිපයක් කරලා Hop Count එක හොයන්න පුලුවන්. ඒ වෙනස්කම් තමයි: 1. Dijkstra's Algorithm එකේදී හොයන්නේ Source Node එකේ සිට graph එකේ අනිත් සියලුම Nodes වලට තියෙන කෙටිම දුර. නමුත් මේ ප්‍රශ්නේදී හොයන්නේ ඕකේ අනිත් පැත්ත. ඒ කියන්නේ දෙන ලද Node එකකට අනිත් සියලුම Nodes වල සිට ඇති Hop Count එක. ඒ නිසා Dijkstra's Algorithm එකේ අදාල තැන් වෙනස් කල යුතුයි. 2. Dijkstra's Algorithm එකේදි nodes අතරේ දුර පෙන්වන්න graph එකක් පාවිච්චි කරනවා වගේ මේ ප්‍රශ්නේදී nodes අතරේ කනෙක්ෂන්ස් පෙන්වන්න Directed Graph එකක් පාවිච්චි කරන්න පුලුවන්. උදා: Node 2 සිට Node 3 දක්වා කනෙක්ෂන් එකක් තියෙන නිසා graph[2,3] = 1 යි නමුත් Node 3 සිට Node 2 දක්වා කනෙක්ෂන් එකක් නැති නිසා graph[3,2] = 0 යි. 3. Dijkstra's Algorithm එකේ Node 0 පාවිච්චි කරනවා නමුත් මේ ප්‍රශ්නේ Node 0 පාවිච්චි කරන්නේ නැති නිසා Dijkstra's Algorithm එකේ අදාල තැන් වෙනස් කල යුතුයි. 4. මේ ප්‍රශ්නේ Node එකකට තව Node එකක් ඩිරෙක්ට් කනෙක්ට් වෙනවානම් Hop Count එක 0 යි. අතරමැද Node 1 ක් හරහා කනෙක්ට් වෙනවානම් Hop Count එක 1 යි. අතර මැද Node 2ක් හරහානම් Hop Count එක 2 යි... ඔය විදියට යන්නේ. ඒක නිසා අපිට අවශ්‍ය Hop Count එක ගන්න Dijkstra's Algorithm එක ඇප්ලයි කරලා එන Hop Count එකෙන් එකක් අඩුකල යුතුයි. Hop Count එක හොයාගත්තට පස්සේ කරන්න තියෙන්නේ node value සහ influence factor එකත් එක්ක දිලා තියෙන ෆෝමියුලා එකට ආදේශ කරලා influence value එක calculate කරන එක. [CODE=csharp]using System; internal class Program { const int INFINITY = int.MaxValue; static int noOfNodes; static int[,] graph; static int mainNode; static decimal influenceFactor; static decimal[] nodeValues; static int[] hopCounts; static decimal[] influenceValues; static int[] FindHopCounts(int[,] graph, int mainNode) { int[] hopCounts = new int[noOfNodes + 1]; bool[] sptSet = new bool[noOfNodes + 1]; for (int i = 1; i <= noOfNodes; i++) { hopCounts[i] = INFINITY; sptSet[i] = false; } hopCounts[mainNode] = 0; for (int count = 1; count <= noOfNodes; count++) { int u = MinHopCountNode(hopCounts, sptSet); sptSet[u] = true; for (int v = 1; v <= noOfNodes; v++) { if (!sptSet[v] && graph[v, u] != 0 && hopCounts[u] != INFINITY && hopCounts[u] + graph[v, u] < hopCounts[v]) { hopCounts[v] = hopCounts[u] + graph[v, u]; } } } for (int i = 1; i <= noOfNodes; i++) { if (i != mainNode && hopCounts[i] != INFINITY) hopCounts[i]--; } return hopCounts; } static int MinHopCountNode(int[] hopCounts, bool[] sptSet) { int minValue = INFINITY, minIndex = -1; for (int v = 1; v <= noOfNodes; v++) if (sptSet[v] == false && hopCounts[v] <= minValue) { minValue = hopCounts[v]; minIndex = v; } return minIndex; } static void CalculateInfluenceValues() { influenceValues = new decimal[noOfNodes + 1]; for (int i = 1; i <= noOfNodes; i++) { if (i != mainNode) { if (hopCounts[i] != INFINITY) { if (hopCounts[i] != 0) influenceValues[i] = nodeValues[i] * influenceFactor * (1m / hopCounts[i]); else influenceValues[i] = decimal.MaxValue; } } } } static void ReadInput() { Console.Write("Input number of nodes: "); noOfNodes = int.Parse(Console.ReadLine()); Console.Write("Input main node: "); mainNode = int.Parse(Console.ReadLine()); Console.Write("Input value for each node: "); string[] strNodeValues = Console.ReadLine().Split(' '); nodeValues = new decimal[noOfNodes + 1]; for (int i = 1; i <= noOfNodes; i++) nodeValues[i] = int.Parse(strNodeValues[i - 1]); Console.Write("Input influence factor: "); influenceFactor = decimal.Parse(Console.ReadLine()); Console.WriteLine("Input the graph of connected nodes:"); graph = new int[noOfNodes + 1, noOfNodes + 1]; for (int i = 1; i <= noOfNodes; i++) { string[] s = Console.ReadLine().Split(','); for (int j = 1; j <= noOfNodes; j++) { graph[i, j] = int.Parse(s[j - 1]); } } } static void PrintResults(int[] hopCounts, int mainNode) { Console.WriteLine(); for (int i = 1; i <= noOfNodes; i++) { if (i != mainNode) { string strHopCount = ""; if (hopCounts[i] == INFINITY) strHopCount = "No path"; else strHopCount = hopCounts[i].ToString(); string strInfluenceValue = ""; if (hopCounts[i] == INFINITY) strInfluenceValue = "No path"; else if (influenceValues[i] == decimal.MaxValue) strInfluenceValue = "Infinity"; else strInfluenceValue = influenceValues[i].ToString(); Console.WriteLine("Hop Count from {0} to {1}: {2}\t\tInfluence value from {3} to {4}: {5}", i, mainNode, strHopCount, i, mainNode, strInfluenceValue); } } } static void Main(string[] args) { ReadInput(); hopCounts = FindHopCounts(graph, mainNode); CalculateInfluenceValues(); PrintResults(hopCounts, mainNode); Console.ReadLine(); } } [/CODE] [ATTACH type="full" alt="Example 1.png"]191454[/ATTACH] [ATTACH type="full" alt="Example 2.png"]191455[/ATTACH] [/QUOTE]

Verification

Hathara warak wissa keeyada? (Hathara wadi karanna 20)

Search

Latest ads

Reply to thread