em có bài tập lớn cltdl&gt nhưng chưa biết gì bác nào giúp em làm bài này với, làm hộ em bằng ngôn ngữ lập trình c đây là gợi ý của cô giáo


6. Đồ thị và bài toán tìm đường đi ngắn nhất
Hãy xem xét một bài toán thực tế về việc chuyển các gói dữ liệu trên một mạng máy tính. Một mạng máy tính bao gồm nhiều các router được nối với nhau thông qua các dây cáp. Một router có thể là nguồn, là đích hoặc là một trạm trung chuyển các gói dữ liệu trên mạng. Một mạng như vậy có thể được hình dung như là một đồ thị với các router là các đỉnh trong đồ thị và các đường nối giữa các router đóng vai trò như là những cung nối các đỉnh trong đồ thị. Một mạng máy tính tuân thủ theo giao thức OPSF tức là sử dụng đường đi ngắn nhất được xác định sử dụng giải thuật Dijkstra.
Trong phạm vi của bài tập lớn này, hãy hình dung mạng là một đồ thị trọng số, vô hướng. Các cung của đồ thị sẽ được gắn một trọng số coi như là thời gian để chuyển một gói dữ liệu bất kỳ giữa hai router được biểu diễn bằng hai đỉnh đầu của cung.

Yêu cầu : Các yêu cầu của bài tập lớn này như sau
• Khai báo và cài đặt cấu trúc dữ liệu ĐỒ THỊ cho phép tạo lập và cập nhật một đồ thị trọng số vô hướng. Mỗi đỉnh của đồ thị được đặc trưng bởi một cái tên là một xâu ký tự chứa các chữ cái hoặc chữ số. Mỗi cung của đồ thị được xác lập bằng một cặp đỉnh và một trọng số là số thực.
• Cài đặt các thao tác cơ bản trên đồ thị như sau
o Khởi tạo một đồ thị ban đầu rỗng
o InsertEdge(Vertex s, Vertex d, float weight) : bổ sung một cung có trọng số w giữa hai đỉnh s, d
o InsertVertex(name) : thêm một đỉnh mới vào đồ thị
o GetWeight(Vertex s, Vertex d): lấy ra trọng số của một cạnh
o ShortestPath (Vertex s, Vertex d) : Tìm đường đi ngắn nhất từ s đến d trong ngữ cảnh hiện tại của đồ thị (cài đặt giải thuật Dijkstra)
o Print: hiển thị hiện trạng của đồ thị
Để sử dụng cho ứng dụng tìm đường truyền trong mạng, cài đặt các thao tác sau:
o EdgeDown(Vertex s, Vertex d) : đánh dấu một cạnh nào đó đang được sử dụng, không dùng được
o EdgeUp(Vertex s, Vertex d) Giải phóng việc sử dụng một cạnh
o VertexDown(name) : Đánh dấu một đỉnh đang được sử dụng
o VertexUp(name) : Giải phóng việc sử dụng một đỉnh, đỉnh này trở nên có thể dùng được

thak nhiều