Extended Euclid: Solving Linear Diophantine Equation

Motivating Problem: Suppose, you are at the invisible cafeteria of CUET. In cafeteria, each cup of tea and coffee cost a and b taka respectively. You can buy any non-negative integer number cups of tea and coffee. If you have c taka, find out if it is possible to buy some cups of tea and coffee spending exactly c taka. We can model this problem like: ax+by=c.

বেলম্যান ফোর্ড(Bellman-Ford) অ্যালগরিদমঃ

Bellman-Ford algorithm solves the single shortest path problem like BFS and Dijkstra. But if the input graph has negative edge weights, Dijkstra fails.

Motivating Problem: Given a weighted, directed Graph G with source s and weight w, the Bellman-Ford algorithm returns a boolean value whether or not there is a

ডায়াক্সট্রা(Dijkstra):

Dijkstra is a shortest path finding algorithm like BFS. BFS works only when the graph is unweighted.But if the graph is weighted, BFS doesn't work correctly. If the edges of a graph is non-negative and weighted, shortest path of the graph can be found by Dijkstra algorithm.

Motivating Problem:Given a weighted graph G and a starting source vertex s,what are the shortest paths from s to the other vertices of G?

স্প্র্যাগ-গ্রান্ডি সংখ্যা

Alice এবং Bob দুই ভাই।তারা এইবার ঈদে সেলামি হিসেবে রিলেটিভদের কাছে থেকে কতগুলো কয়েন পেয়েছে।কিন্তু তারা খেলনা উড়োজাহাজ কিনতে গিয়ে দেখল একজনের কয়েন দিয়ে কেনা যাচ্ছে না।তাই তারা দুজনের কয়েন গুলো এক জায়গায় রেখে স্তুপ করল এবং একটা গেম খেলার সিদ্ধান্ত নিল।খেলায় যে জিতবে সে সবগুলো নিয়ে নিবে,মানে উড়োজাহাজ তার। গেমটা হল তারা প্রতি চালে স্তুপ থেকে ১,২,অথবা ৩ টা কয়েন তুলে নিতে পারবে,শেষ কয়েন টা যে তুলতে পারবে সে জিতে যাবে।এখন কয়েনের সংখ্যা দেখেই তোমাকে বলতে হবে কে জিতবে(তারা কেউ কোন ভুল চাল দিবে না)।