Graph Theory - Dijkstra Algorithm (Arabic)

Content Link: www.dropbox.co...
Content:
Shortest Paths Facts
Relaxation
Dijkstra Proof
O(V^2) Algorithm for Adjacency Matrix
O(E logV) Algorithm for Adjacency List
Problems: UVA(429, 762, 10113, 10436, 10525, 10801, 10947, 10959, 10986)

[@zaidrj7374]

أنا بستخدم جافا بالبرمجة , لكن مع ذلك بفهم الفكرة الأساسية منك بطريقة تمكني من الاستغناء عن فهم الكود بال C++ بشكل جزئي ,سواء بهاد الدرس أو بغيره, من قلبي بحب أقلك الله يجزيك الخير.

[@abdelrhman_sasalh3522]

how do i add the value in "adjMax" that we are supposed to use "vector" not -> "vector adjMax". min 13:52

[@ArabicCompetitiveProgramming]

a[i][j] = make_pair(2, 3);

[@prodev7401]

NOTE : in some graph work with négative weight but not every time ;)

[@ArabicCompetitiveProgramming]

True, but they are very little graphs...specifically when the a path through negative edge doesn't yield shorter road, probably Dijsktra will work.

[@prodev7401]

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

[@ArabicCompetitiveProgramming]

Pro Dev Graph (1, 2, 10), (2, 3, -100), (3, 4, 7) => Dijkstra works

[@prodev7401]

yes i know thanks ;)))

[@hossamahmed4936]

Good explanation but your code works on -ve edges also not as you said in the start of the video

[@ArabicCompetitiveProgramming]

no

[@ayasaber2567]

Good work MSA but i have an question : what does "adjMax" Specifically contain ?

[@ArabicCompetitiveProgramming]

+aya saber Adjacency Matrix Representation en.wikipedia.org/wiki/Adjacency_matrix

[@ayasaber2567]

+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?

[@ArabicCompetitiveProgramming]

+aya saber intialize whole array with some flag (say 10000000) read each line then adj[src][dest] = weight

[@fadysamy1542]

Can you write the equality which used to calculate order of Dijkstra2() ,which is O(Elog V)?

[@ArabicCompetitiveProgramming]

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

[@MsAmrsamy]

what about if there are many shortest path from source to destination, how can i get them all?

[@ArabicCompetitiveProgramming]

en.wikipedia.org/wiki/K_shortest_path_routing

[@yahyaadel6933]

Dropbox link is 404 , is there any update on the content hosting ?

[@ArabicCompetitiveProgramming]

Find github link from channel about

[@mohamedhany9561]

Good work\

[@moazeldfrawy7733]

thanks a lot