Dijkstra’s Algorithm সহজ ভাষায়

Graph Theory শেখার সময় সবচেয়ে গুরুত্বপূর্ণ Algorithm-গুলোর একটি হলো Dijkstra’s Algorithm।

অনেকের কাছেই Algorithm-টি প্রথমে বেশ কঠিন মনে হয়। কিন্তু যদি এটাকে বাস্তব জীবনের একটি উদাহরণের সাথে মিলিয়ে দেখা যায়, তাহলে বিষয়টি অনেক সহজ হয়ে যায়।

আজ আমি ঠিক সেই চেষ্টাই করবো।

উদাহরণ

কিছুদিন আগে জাদু PC নিয়ে একটি Event হয়েছিল।

ধরুন আপনি একজন Student।

আপনার Budget খুবই কম। ৩০–৪০ হাজার টাকা দিয়ে PC বানানোর মতো সামর্থ্য নেই। তাই ১০ হাজার টাকার Setup-এর কথা শুনে আপনিও Event-এ অংশগ্রহণ করার সিদ্ধান্ত নিলেন।

সমস্যা হলো—

Event হবে গুলশানে
আপনি থাকেন পুরান ঢাকা (লালবাগ)-এ
আপনার কাছে Smartphone-ও নেই, তাই Google Maps ব্যবহার করার সুযোগও নেই।

তাই Event-এর দিন আপনি সকাল সকাল বের হয়ে গেলেন এবং মানুষের কাছে রাস্তা জিজ্ঞেস করতে শুরু করলেন।

আপনার লক্ষ্য একটাই—

সবচেয়ে কম খরচে গুলশানে পৌঁছানো।

রাস্তার Map

নিচের Diagram-এ বিভিন্ন Location এবং তাদের মধ্যে যাতায়াতের ভাড়া দেখানো হয়েছে।

                 পুরান ঢাকা
                /          \
             ১০            ২০
              /              \
ঢাকা বিশ্ববিদ্যালয় ------- কাকরাইল
      |   \              /   \
    ১০    ২৫          ৫     ২০
      |       \        /       |
      |      মালিবাগ রেলগেট   |
      |            \      |     |
      |             \    ২০     ২৫
      |              \    |     |
      └────────────── মৌচাক ─────┘
                           |
                          ৩০
                           |
                        গুলশান

ছবির Graph (Image থেকে)

নিচের Diagram-টি Image অনুযায়ী Markdown আকারে উপস্থাপন করা হলো।

From	To	Cost
পুরান ঢাকা	ঢাকা বিশ্ববিদ্যালয়	১০
পুরান ঢাকা	কাকরাইল	২০
ঢাকা বিশ্ববিদ্যালয়	কাকরাইল	১০
ঢাকা বিশ্ববিদ্যালয়	মৌচাক	২৫
কাকরাইল	মৌচাক	৫
কাকরাইল	মালিবাগ রেলগেট	১০
মৌচাক	মালিবাগ রেলগেট	০ (হেঁটে যাওয়া যায়)
মৌচাক	গুলশান	২৫
মালিবাগ রেলগেট	গুলশান	২০

Note: উপরের তথ্যগুলো আপনার দেওয়া Hand-drawn Diagram-এর ভিত্তিতে লেখা হয়েছে।

Step 1

আপনি শুরু করলেন পুরান ঢাকা থেকে।

দুটি রাস্তা আছে—

গন্তব্য	ভাড়া
ঢাকা বিশ্ববিদ্যালয়	১০ টাকা
কাকরাইল	২০ টাকা

যেহেতু আপনি সবচেয়ে কম খরচের পথ খুঁজছেন, তাই আপনি ঢাকা বিশ্ববিদ্যালয়-এ গেলেন।

এখন আপনি Mark করে রাখলেন—

✅ পুরান ঢাকা
✅ ঢাকা বিশ্ববিদ্যালয়

Step 2

এখন আপনি ঢাকা বিশ্ববিদ্যালয়ে।

এখান থেকে যাওয়া যায়—

গন্তব্য	ভাড়া
পুরান ঢাকা	১০
কাকরাইল	১০
মৌচাক	২৫

পুরান ঢাকা আপনি ইতোমধ্যে Visit করেছেন।

তাই সেটি বাদ দিলেন।

এখন সবচেয়ে কম খরচের রাস্তা—

কাকরাইল (১০ টাকা)

আপনি সেখানে চলে গেলেন।

Step 3

এখন আপনি কাকরাইলে।

এখান থেকে যাওয়া যায়—

গন্তব্য	ভাড়া
পুরান ঢাকা	২০
ঢাকা বিশ্ববিদ্যালয়	১০
মৌচাক	৫
মালিবাগ রেলগেট	১০

পুরান ঢাকা এবং ঢাকা বিশ্ববিদ্যালয় আগেই Visit করা হয়েছে।

তাই বাকি রইলো—

মৌচাক (৫)
মালিবাগ রেলগেট (১০)

যেহেতু ৫ টাকা কম লাগে,

আপনি মৌচাক-এ চলে গেলেন।

Step 4

এখন আপনি মৌচাকে।

এখান থেকে যাওয়া যায়—

গন্তব্য	ভাড়া
ঢাকা বিশ্ববিদ্যালয়	২৫
কাকরাইল	৫
মালিবাগ রেলগেট	০ (হেঁটে যাওয়া যায়)
গুলশান	২৫

যেহেতু মালিবাগ রেলগেট একদম কাছেই এবং হেঁটে যাওয়া যায়,

আপনি ০ টাকা খরচে মালিবাগ রেলগেট চলে গেলেন।

Step 5

এখন আপনি মালিবাগ রেলগেটে।

এখান থেকে যাওয়া যায়—

গন্তব্য	ভাড়া
কাকরাইল	১০
মৌচাক	০
গুলশান	২০

কাকরাইল এবং মৌচাক আগে থেকেই Visit করা হয়েছে।

তাই একমাত্র নতুন রাস্তা—

গুলশান (২০ টাকা)

আপনি অবশেষে গুলশানে পৌঁছে গেলেন।

Shortest Path

অবশেষে আপনার পাওয়া সবচেয়ে কম খরচের পথ হলো—

পুরান ঢাকা
      │
     ১০
      │
ঢাকা বিশ্ববিদ্যালয়
      │
     ১০
      │
কাকরাইল
      │
      ৫
      │
মৌচাক
      │
      ০
      │
মালিবাগ রেলগেট
      │
     ২০
      │
   গুলশান

মোট খরচ—

10 + 10 + 5 + 0 + 20 = 45 টাকা

এখান থেকে কী শিখলাম?

এতক্ষণে আপনি আসলে একটি গুরুত্বপূর্ণ বিষয় শিখেছেন।

প্রতিবার আপনি—

সবচেয়ে কম Cost-এর Node নির্বাচন করেছেন।
যেসব জায়গা আগে Visit করেছেন, সেগুলো আবার Visit করেননি।
প্রতিটি নতুন Node-এ পৌঁছে তার Neighbor-গুলো Compare করেছেন।
ধীরে ধীরে Destination পর্যন্ত সবচেয়ে কম খরচের পথ বের করেছেন।

এটাই মূলত Dijkstra’s Algorithm-এর মূল ধারণা।

Dijkstra’s Algorithm-এর মূল ধারণা

Algorithm-টি প্রতিবার—

সবচেয়ে কম Distance-এর Unvisited Node নির্বাচন করে।
সেটিকে Visited হিসেবে Mark করে।
তার Neighbor-গুলোর Distance Update করে।
সব Node Visit না হওয়া পর্যন্ত Process চালিয়ে যায়।

Time Complexity

Implementation	Complexity
Simple Array	O(V²)
Priority Queue (Min Heap)	O((V + E) log V)

Python Implementation

নিচে Dijkstra’s Algorithm-এর একটি সাধারণ Python Implementation দেওয়া হলো।

import sys

vertices = [
    [0, 0, 1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0, 1, 0],
    [1, 1, 0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0, 0, 1],
    [0, 0, 1, 0, 0, 1, 0],
    [0, 1, 0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0, 1, 0]
]

edges = [
    [0, 0, 1, 2, 0, 0, 0],
    [0, 0, 2, 0, 0, 3, 0],
    [1, 2, 0, 1, 3, 0, 0],
    [2, 0, 1, 0, 0, 0, 1],
    [0, 0, 3, 0, 0, 2, 0],
    [0, 3, 0, 0, 2, 0, 1],
    [0, 0, 0, 1, 0, 1, 0]
]

def to_be_visited():
    global visited_and_distance
    v = -1
    for index in range(num_of_vertices):
        if visited_and_distance[index][0] == 0 and (
            v < 0 or visited_and_distance[index][1] <= visited_and_distance[v][1]
        ):
            v = index
    return v

num_of_vertices = len(vertices[0])

visited_and_distance = [[0, 0]]

for _ in range(num_of_vertices - 1):
    visited_and_distance.append([0, sys.maxsize])

for _ in range(num_of_vertices):
    to_visit = to_be_visited()

    for neighbor_index in range(num_of_vertices):
        if (
            vertices[to_visit][neighbor_index] == 1
            and visited_and_distance[neighbor_index][0] == 0
        ):
            new_distance = (
                visited_and_distance[to_visit][1]
                + edges[to_visit][neighbor_index]
            )

            if visited_and_distance[neighbor_index][1] > new_distance:
                visited_and_distance[neighbor_index][1] = new_distance

    visited_and_distance[to_visit][0] = 1

for i, distance in enumerate(visited_and_distance):
    print(
        f"Distance of {chr(ord('A') + i)} from source vertex: {distance[1]}"
    )

উপসংহার

Dijkstra’s Algorithm প্রথম দেখায় কিছুটা জটিল মনে হলেও, বাস্তবে এটি খুবই স্বাভাবিক একটি ধারণার উপর কাজ করে—প্রতিবার সবচেয়ে কম খরচের পথটি বেছে নিয়ে ধীরে ধীরে Destination-এর দিকে এগিয়ে যাওয়া।

Google Maps, Ride Sharing App, GPS Navigation, Network Routing এবং অসংখ্য Real-world System-এ এই Algorithm বা এর উন্নত সংস্করণ ব্যবহার করা হয়।

Graph Theory শেখার ক্ষেত্রে Dijkstra’s Algorithm একটি মৌলিক এবং অত্যন্ত গুরুত্বপূর্ণ বিষয়। এর মূল ধারণাটি একবার পরিষ্কার হয়ে গেলে পরবর্তীতে Shortest Path সম্পর্কিত আরও অনেক Algorithm শেখা অনেক সহজ হয়ে যায়।