|
I have been reading this:https://en.wikipedia.org/wiki/Dijkstra's_algorithm[^]. It says,
Dijkstra's original algorithm does not use a min-priority queue and runs in time O(|V|^2) (where |V| is the number of nodes). The idea of this algorithm is also given in (Leyzorek et al. 1957). The implementation based on a min-priority queue implemented by a Fibonacci heap and running in O(|E|+|V|\log|V|) (where |E| is the number of edges) is due to (Fredman & Tarjan 1984). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.
But whether or not we use a min-priority queue, shouldn't it be O(|V|^2) ?
Lets consider the situation where every node in the graph is connected to every other node. And each of this node is double ended (i.e., if there is a link from A to B then there is also a link from B to A). If we were to make the algorithm update the distance of every node (from the source) then shouldn't we obviously be checking |V| nodes for each node in the graph? We need to compulsorily check each node for every other node we visit!
Now following this algorithm from Wikipedia:
1 function Dijkstra(Graph, source):
2 dist[source] ← 0 // Initialization
3
4 create vertex set Q
5
6 for each vertex v in Graph:
7 if v ≠ source
8 dist[v] ← INFINITY // Unknown distance from source to v
9 prev[v] ← UNDEFINED // Predecessor of v
10
11 Q.add_with_priority(v, dist[v])
12
13
14 while Q is not empty: // The main loop
15 u ← Q.extract_min() // Remove and return best vertex
16 for each neighbor v of u: // only v that is still in Q
17 alt = dist[u] + length(u, v)
18 if alt < dist[v]
19 dist[v] ← alt
20 prev[v] ← u
21 Q.decrease_priority(v, alt)
22
23 return dist[], prev[]
We can obviously see that the loop continues until all nodes in Q are visited. During each visit, every neighbor of v is checked. So this clearly checks every other node in the graph for each node that's visited (if we assume that every node is connected to every other node). So now we have,
O(|V|^2)
instead of,
O(|E|+|V|log|V|)
Where did I go wrong?
|
|
|
|
|
I guess, by know I got to know the answer myself! The mistake I initially did was, I neglected the |E| in O(|E|+|V|log|V|). In the worst case, we can consider O(|E|) to be O(|V|^2). But still, we treat |E| as a separate variable because, |E| <= (|V|^2- |V|)/2. Though there is an upper bound for |E|, it is still independent of |V|. I have explained this well in my blog: http://www.creativitymaximized.com/2015/10/shortest-path-algorithm-elaborated.html[^]
|
|
|
|
|
Hello,I understand Shell Sort definition but I can not understand
this C# code:
public void shellSort()
{
int inner, outer;
long temp;
int h = 1;<br />
while(h <= nElems/3)
h = h*3 + 1;
while(h>0)<br />
{
for(outer=h; outer<nElems; outer++)
{
temp = theArray[outer];
inner = outer;
while(inner > h-1 && theArray[inner-h] >= temp)
{
theArray[inner] = theArray[inner-h];
inner -= h;
}
theArray[inner] = temp;
} // end for
h = (h-1) / 3;<br />
} // end while(h>0)
} // end shellSort()
please help me thx!
|
|
|
|
|
Member 11760977 wrote: but I can not understand
this C# code:
You'll have to give us a specific question if we're going to help you.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Member 11760977 wrote: but I can not understand this C# code:
Why don't you let the code show you how it works ?
Use the debugger ! You will see the code doing its stuff. Run the code step by step and inspect variables.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
|
Why do you give me this link ?
I know how it works !
My previous message was giving a way to see the program doing its stuff.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Quisiera saber quien tiene el algoritmo de Ford y Fulkerson , he estado buscando en varias paginas este algoritmo, pero no logro conseguir.Si alguien lo puede conseguir lo antes posible o hacerlo estaría muy agradecido.
|
|
|
|
|
This is an English language site. You'll get few responses for postings in other languages.
Bing Translator:
I would like to know who has the algorithm of Ford and Fulkerson, I've been searching several pages this algorithm, but I can not get. If someone can obtain as soon as possible or make it I would be very grateful.
Ford--Fulkerson_algorithm[^] on Wikipedia has an explanation as well as a Python implementation. For other languages, you're on your own...
(This "smells" a bit like homework. If so, you really need to do it yourself!)
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
This is still an English language site, and the answers haven't changed since last Thursday[^].
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
A directed graph is called a unique-path graph if given vertices v and w, there is at most one path from v to w. Now, I am given a graph G in which there exists a vertex x that has paths to all other vertices. (The vertex x is not known to us initially) How do I check that G is a unique path graph in O(|E| + |V|) time?
Using the concept of strongly connected components, I can find the vertex x in O(|E|+|V|) time. How do I proceed after that? How does x help us in checking multiple paths between a pair of vertices?
|
|
|
|
|
What data do you have about the graph ? got a example ?
Have you tried something ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Hi All,
I am trying to come up with an algorithm to get following three piece of information to plot a chart:
1. Start : Should be close to the minimum value of the dataset
2. Stop : Should be close to the maximum value of the dataset
3. Interval : Should be such that it will have "0" on the axis when interval traverses from minimum to maximum.
Example: dataset{-266,-17.6,0.5,2000,6000}
My final return values should be:
Start: 400
Stop: 6000
Interval:200
Note: Since start is 400 and interval is 200, we will have 0 as a point on the x-axis.
|
|
|
|
|
How did you choose 400 to be 'close' to -266? Plotting the values from 400 to 6000 in intervals of 200 is a simple straight line. Your question is not clear.
|
|
|
|
|
400 value is in example. I came up with those numbers to explain what I am trying to achieve.
Actually, I did figure this out.
Thanks.
|
|
|
|
|
Hi all!
when this impulse based equation can equal to zero:
w'=w+(j/I)*r*n;
n normal contact;j impulse;I inertia;
modified 1-Sep-15 19:43pm.
|
|
|
|
|
What is your question ?
And I guess more details will be welcomed.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
as you know: https://en.wikipedia.org/wiki/Collision_response[^]
just that w will never be zero, and need always two points of contact to be;(the eqation above is elastic collision with rotation no friction)!
__________ \/__________
a triangle can never stand like this!(in a real world or can it!?)
see here(http://i.stack.imgur.com/o9P7V.png[^]
what if the ball was heading the center of the bar, the bar won't spin right!
but we know that a force in a direction in a center of mass mmake angular velocity zero right!
but this equation from wiki never make it until there is two points of contact, is that is!?
modified 2-Sep-15 8:34am.
|
|
|
|
|
Ok, the wording is not obvious for not English native people.
A couple of sentences explaining what you are looking for will not arm.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
|
Good day,
I have a DB, that have a 3000 strings and 40 integer columns, each of them describe something about 1 piece of product, for example, cost, resource, etc.
User type end sum for each column.
I need a feedback, what stack of 5 types of instruments fits max by each column to the user number.
For example, 7 hammers, 2 presses, 3 crowbar, 4 gloves, 5 glasses all together cost 154000 money, user input 150000, have a resource of 923000 hours, user input 920000 etc.
I don't know, how to google that question or use search for it, but if you can help me with it's name or, more of it, with building, i will release my end program under Open Source. Thank you very much for your time, sorry, if my English bad.
|
|
|
|
|
Knapsack problem? Bin packing?
|
|
|
|
|
It is looking like HomeWork !
I think some details are missing in the problem to fully understand what is the request?
It look like a simple counting problem.
What have you tried ? What is your problem ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Good day,
You can solve this problem by integer linear programming.
|
|
|
|
|
It is more like counting things.
like making a list of all names, and counting each you see a name
and printing the top 5 names.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|