[Help] Giải thuật tìm tất cả đường đi trên 1 đồ thị

[ndp1007]

Mình có một bài toán tìm đường đi
Hình ảnh đồ thị như sau:
http://i581.photobucket.com/albums/ss259/ndp1007/10hc_hcmus/Graph.png
Chuyển sang ma trận kề các trọng số :

9
0 2 1 0 0 0 0 0 10
0 0 0 3 0 0 0 0 0
0 1 0 4 0 0 0 0 9
0 0 0 0 1 3 0 0 5
0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0
0 8

Yêu cầu của bài toán là tìm tất cả các đường đi có thể đi từ Đỉnh đầu --> Đỉnh cuối cho trước .

Ví dụ đỉnh đầu đỉnh cuối là 0-8 thì kết quả là :


0 8
0 2 8
0 1 3 8
0 2 3 8
0 2 1 3 8
0 1 3 4 6 7 8
0 2 3 4 6 7 8
0 2 1 3 4 6 7 8
Tổng cộng có 8 đường đi, và số lượng đỉnh mỗi đường đều khác nhau.

Mong các bạn chia sẽ ý tưởng, hay một vài dòng code gợi ý.
Cảm ơn các bạn rất nhiều :)

[matxich.net]

Tôi có ý tưởng như hình vẽ dưới, chẳng qua đó là viết ra mô hình trạng thái của 1 đồ thị ở dạng cây.

http://i1184.photobucket.com/albums/z338/imatxich/CNTT/Dijkstra_Avanced.png
Gợi ý hi vọng bạn viết được code :D

Nhưng mình trước tiên muốn viết nên thử làm bài nốt nhạc dạo đầu này, xem sao đã mới tiếp tục được bản hòa tấu trên lol

http://i1184.photobucket.com/albums/z338/imatxich/CNTT/LTDT_Notnhacdaodau.png

Yêu cầu : Tìm đường đi ngắn nhất từ một đỉnh vStart cho trước đến tất cả các đỉnh còn lại.
Qui tắc Output :
+ Dòng 1 : vStart --> vEnd
+ Dòng 2 : Chi phí ngắn nhất từ vStar --> vEnd
+ Dòng 2 : Chi tiết về đường đi

Làm dạng hướng đối tượng cho dễ, và thay mảng = vector để tối ưu vung nhớ
1. Xây dựng lớp Graph


#define VOCUNG 1000
#include<vector>
using namespace std;
class Graph
{
private:
int n;
vector<vector<int>> W;
vector<int> L;
vector<int> Labels;
vector<int> V;
int vStart,vEnd;
vector<int> minRoute;
public:
Graph(void);
~Graph(void);
void rFile(char*);
void wFile(char*,int,int);
void viewW();
void viewV();
void viewLabels();
void viewL();
void viewRoute();
int fMin();
void Install(int);
void Dijkstra(int vStart, int vEnd);
void copyRoute(int[],vector<int>&);
void Run(char*, char*);
};

........
Hẹn vài ngày nữa sẽ cặn kẽ hơn bây giờ bận việc rồi
See you agian !

[vthanh_88]

Nếu là tìm đường đi ngắn nhất thì dùng thuật toán di truyền. Với dữ liệu lớn thì mấy thuật toán trên chạy chậm lắm.Bài toàn giống bài tìm đường đi trên thành phố.Nếu thành phố thật thì chờ tìm xong chắc đi ngủ rùi.

[sangbenh]

thanksssssssssssssssssssssssssssss

[hero_vnz]

bài làm của bạn khá hay, cảm ơn bạn nhiều nha.

Tôi có ý tưởng như hình vẽ dưới, chẳng qua đó là viết ra mô hình trạng thái của 1 đồ thị ở dạng cây.

http://i1184.photobucket.com/albums/z338/imatxich/CNTT/Dijkstra_Avanced.png
Gợi ý hi vọng bạn viết được code :D

Nhưng mình trước tiên muốn viết nên thử làm bài nốt nhạc dạo đầu này, xem sao đã mới tiếp tục được bản hòa tấu trên lol

http://i1184.photobucket.com/albums/z338/imatxich/CNTT/LTDT_Notnhacdaodau.png

Yêu cầu : Tìm đường đi ngắn nhất từ một đỉnh vStart cho trước đến tất cả các đỉnh còn lại.
Qui tắc Output :
+ Dòng 1 : vStart --> vEnd
+ Dòng 2 : Chi phí ngắn nhất từ vStar --> vEnd
+ Dòng 2 : Chi tiết về đường đi

Làm dạng hướng đối tượng cho dễ, và thay mảng = vector để tối ưu vung nhớ
1. Xây dựng lớp Graph


#define VOCUNG 1000
#include<vector>
using namespace std;
class Graph
{
private:
int n;
vector<vector<int>> W;
vector<int> L;
vector<int> Labels;
vector<int> V;
int vStart,vEnd;
vector<int> minRoute;
public:
Graph(void);
~Graph(void);
void rFile(char*);
void wFile(char*,int,int);
void viewW();
void viewV();
void viewLabels();
void viewL();
void viewRoute();
int fMin();
void Install(int);
void Dijkstra(int vStart, int vEnd);
void copyRoute(int[],vector<int>&);
void Run(char*, char*);
};

........
Hẹn vài ngày nữa sẽ cặn kẽ hơn bây giờ bận việc rồi
See you agian !

[auauau97]

Tôi có ý tưởng như hình vẽ dưới, chẳng qua đó là viết ra mô hình trạng thái của 1 đồ thị ở dạng cây.

http://i1184.photobucket.com/albums/z338/imatxich/CNTT/Dijkstra_Avanced.png
Gợi ý hi vọng bạn viết được code :D

Nhưng mình trước tiên muốn viết nên thử làm bài nốt nhạc dạo đầu này, xem sao đã mới tiếp tục được bản hòa tấu trên lol

http://i1184.photobucket.com/albums/z338/imatxich/CNTT/LTDT_Notnhacdaodau.png

Yêu cầu : Tìm đường đi ngắn nhất từ một đỉnh vStart cho trước đến tất cả các đỉnh còn lại.
Qui tắc Output :
+ Dòng 1 : vStart --> vEnd
+ Dòng 2 : Chi phí ngắn nhất từ vStar --> vEnd
+ Dòng 2 : Chi tiết về đường đi

Làm dạng hướng đối tượng cho dễ, và thay mảng = vector để tối ưu vung nhớ
1. Xây dựng lớp Graph


#define VOCUNG 1000
#include<vector>
using namespace std;
class Graph
{
private:
int n;
vector<vector<int>> W;
vector<int> L;
vector<int> Labels;
vector<int> V;
int vStart,vEnd;
vector<int> minRoute;
public:
Graph(void);
~Graph(void);
void rFile(char*);
void wFile(char*,int,int);
void viewW();
void viewV();
void viewLabels();
void viewL();
void viewRoute();
int fMin();
void Install(int);
void Dijkstra(int vStart, int vEnd);
void copyRoute(int[],vector<int>&);
void Run(char*, char*);
};

........
Hẹn vài ngày nữa sẽ cặn kẽ hơn bây giờ bận việc rồi
See you agian !
bài này khá hay đó, phải nghiên cứu thêm mới được !

[ebookfinder]

các bạn mất công thiết kế 1 thuật toán mới trong khi chỉ cần chỉnh sửa Dijkstra là đủ; trong phần push cái đỉnh là cạnh liên quan vào CLOSE, các bạn đặt nó lại OPEN mà set cái cạnh = 1 số cực lớn (MAXINT, DBLMAX...)