Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: bài toán tìm đừong đi ngắn nhất bằng thuật toán FLoyd , đoạn code C++ bị lỗi các bạn xem giúp mình

  1. #1
    Ngày gia nhập
    03 2012
    Bài viết
    0

    Arrow bài toán tìm đừong đi ngắn nhất bằng thuật toán FLoyd , đoạn code C++ bị lỗi các bạn xem giúp mình

    Code:
    #include<stdio.h>
    #include<conio.h>
    # define MAX 20
    # define vc 1000
    int a[MAX][MAX],g[MAX][MAX];
    int n;
    void nhap(int &n)
    {
    	int m;
            int h;
    	int Graph[][3]={{1,2,4},{1,3,1},{2,4,5},{2,5,3},{3,4,10},{3,2,2},{4,6,9},{5,4,4},{5,6,7},{6,2,6}};
            int Graph1[][3]={{1,2,2},{1,3,3},{2,4,4},{2,5,5},{3,4,4},{3,2,2},{4,6,6},{5,4,4},{5,6,6},{6,2,2}};
    	n=6;
    	m=sizeof(Graph)/sizeof(Graph[0]);
    	h=sizeof(Graph)/sizeof(Graph1[0]);
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    			a[i][j]=0;
    	for(i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    			g[i][j]=0;     	
    	int x,y,z;
    	for(i=0;i<m;i++)
    	{
    		x=Graph[i][0];
    		y=Graph[i][1];
    		z=Graph[i][2];
    		a[x][y]=z;
    	}
    	for(i=0;i<h;i++)
    	{
    		x=Graph1[i][0];
    		y=Graph1[i][1];
    		z=Graph1[i][2];
    		g[x][y]=z;
    	}
    }
    void init()
    {
    	int n=6;
    	for(int i=1;i<=n ;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    		    if(a[i][j]==0)
    			a[i][j]=vc;
                        a[i][i]=0;
    		}
    	}
    }
    void xuat(int n)
    {
    	for(int i=1;i<=n;i++)
    	{
            	printf("\n");
    		for(int j=1;j<=n;j++)
    		{
    			printf("%8d",a[i][j]);
                    }
    	}
    
    	for(i=1;i<=n ;i++)
    	{
            	printf("\n");
    		for(int j=1;j<=n;j++)
    			printf("%3d",g[i][j]);
    	}
    }
    void floy()
    {
    	xuat(n);
            int x,y;
    	printf("\nNhap diem bat di: ");
    	scanf("%d",&x);
    	printf("\nNhap diem den: ");
    	scanf("%d",&y);
    	for(int k=1;k<=n;k++)
    		for(int i=1;i<=n;i++)
    			for(int j=1;j<=n;j++)
    				if(a[i][j] > a[i][k]+a[k][j])
    				{
    					a[i][j]=a[i][k]+a[k][j];
    					g[i][j]=g[i][k];
    				}
    	if(a[x][y]!=vc)
    	{
    		printf("\nduong di ngan nhat tu %d den %d la ",x,y);
    		printf("%d",x);
    		while(g[x][y]!=y)
    		{
    			x=g[x][y];
    			printf("->%d",x);
    		}
            printf("->%d",y);
            }
    }
    void main()
    {
        clrscr();
        int i;
    	nhap(n);
    	init();
        floy();
    	getch();
    }
    " alt="Công thức toán học Latex" border="0" />

  • #2
    Ngày gia nhập
    03 2012
    Bài viết
    0

    Bài toán tìm đường đi ngắn nhất cho tất cả các cặp đỉnh trong một đồ thị để giải

    ++

    for y:=1 to V do

    for x:= 1 to V do

    if a[x,y]>0 then

    for j:=1 to V do

    if a[y,j]>0 then

    if (a[x,j]=0) or (a[x,y]+a[y,j]

    then a[x,j]:= a[x,y]+a[y,j];

    ++

    Cấu trúc của thuật toán dùng phép logic “or” để theo dõi các đường đi, chúng ta thêm một ít tính toán cho mỗi cạnh để xác định xem nó có là bộ phận của đường đi ngắn nhất mới hay không: “ đường đi ngắn nhất từ nút x tớinút j chỉ đi qua các nút có chỉ số nhỏ hơn y+1 thì hoặc là đường đi ngắn nhất từ nút x tới nút j chỉ đi qua các nút có chỉ số nhỏ hơn y hoặc nếu ngắn hơn thì nó là đường đi ngắn nhất từ x tới y cộng vớiđường đi ngắn nhất từ y tới j”. Phần tử 0 trong ma trận tương ứng không có cạnh nối hai đỉnh, chương trình có thể cải tiến đơn giản hơn (bỏ đi các phép so sánh với 0) bằng cách dùng một biến để ký hiệu cạnh có trọng số vô hạn.

  • Các đề tài tương tự

    1. Tìm đường đi ngắn nhất bằng giải thuật Ford Bellman (Source code C#)
      Gửi bởi regulus trong diễn đàn Dự án & Source code C#, ASP.NET
      Trả lời: 7
      Bài viết cuối: 14-11-2013, 10:56 AM
    2. Đường đi ngắn nhất = giải thuật dijkstra trong Dev C,xem & sửa giúp em với..outtime
      Gửi bởi minhtoan991 trong diễn đàn Nhập môn lập trình C/C++
      Trả lời: 1
      Bài viết cuối: 01-04-2011, 06:12 PM
    3. giải thuật Floyd tìm đường đi ngắn nhất
      Gửi bởi nguoikhonglo171 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
      Trả lời: 0
      Bài viết cuối: 25-03-2011, 11:40 AM
    4. Làm thế nào để xuất đường đi ngắn nhất dùng Floyd?
      Gửi bởi PDV trong diễn đàn Nhập môn lập trình C/C++
      Trả lời: 3
      Bài viết cuối: 20-12-2008, 12:02 AM
    5. Ngắt trong C, Giúp chỉnh sửa code về ngắt
      Gửi bởi darkryte trong diễn đàn Nhập môn lập trình C/C++
      Trả lời: 3
      Bài viết cuối: 17-11-2007, 07:21 PM

    Quyền hạn của bạn

    • Bạn không thể gửi đề tài mới
    • Bạn không thể gửi bài trả lời
    • Bạn không thể gửi các đính kèm
    • Bạn không thể chỉnh sửa bài viết của bạn