As I remember, we iterate on all edges and push them in the queue (each edge processed twice). This is ElogE In worst case, E=V^2. Log(E) = 2LogV = LogV so we write it ELogV consider also, we iterate on every node once. Total is O(ElogV + V), for shor O(Elogv) other implementations will have different implementations
أنا بستخدم جافا بالبرمجة , لكن مع ذلك بفهم الفكرة الأساسية منك بطريقة تمكني من الاستغناء عن فهم الكود بال C++ بشكل جزئي ,سواء بهاد الدرس أو بغيره, من قلبي بحب أقلك الله يجزيك الخير.
+Arabic Competitive Programming if i have file contains many lines , each line formed ->>"source node , destination node , weight" how i can fill -> adjMax, dist , in code?
because my freinds At the university they said it's impossible :D the problem in the relaxation STEP that's why bellman-ford works because every time relax ALL edges
how do i add the value in "adjMax" that we are supposed to use "vector" not -> "vector adjMax". min 13:52
a[i][j] = make_pair(2, 3);
Can you write the equality which used to calculate order of Dijkstra2() ,which is O(Elog V)?
As I remember, we iterate on all edges and push them in the queue (each edge processed twice). This is ElogE
In worst case, E=V^2. Log(E) = 2LogV = LogV
so we write it ELogV
consider also, we iterate on every node once. Total is O(ElogV + V), for shor O(Elogv)
other implementations will have different implementations
أنا بستخدم جافا بالبرمجة , لكن مع ذلك بفهم الفكرة الأساسية منك بطريقة تمكني من الاستغناء عن فهم الكود بال C++ بشكل جزئي ,سواء بهاد الدرس أو بغيره, من قلبي بحب أقلك الله يجزيك الخير.
Good explanation but your code works on -ve edges also not as you said in the start of the video
no
Dropbox link is 404 , is there any update on the content hosting ?
Find github link from channel about
Good work MSA
but i have an question :
what does "adjMax" Specifically contain ?
+aya saber
Adjacency Matrix Representation
en.wikipedia.org/wiki/Adjacency_matrix
+Arabic Competitive Programming
if i have file contains many lines , each line formed ->>"source node , destination node , weight"
how i can fill -> adjMax, dist , in code?
+aya saber
intialize whole array with some flag (say 10000000)
read each line
then
adj[src][dest] = weight
what about if there are many shortest path from source to destination, how can i get them all?
en.wikipedia.org/wiki/K_shortest_path_routing
NOTE : in some graph work with négative weight but not every time ;)
True, but they are very little graphs...specifically when the a path through negative edge doesn't yield shorter road, probably Dijsktra will work.
because my freinds At the university they said it's impossible :D the problem in the relaxation STEP that's why bellman-ford works because every time relax ALL edges
Pro Dev
Graph (1, 2, 10), (2, 3, -100), (3, 4, 7) => Dijkstra works
yes i know thanks ;)))
Good work\
thanks a lot