матрица смежности

Question

Учитывая матрицу смежности графа и положительное целое число n, найти номер пути длины n между двумя вершинами, я не знаю, как преобразовать в программирование?

Answer 1

Я предполагаю, что это домашнее задание, так что вот подсказка. Если бы вам дали карандаш, бумагу и небольшую матрицу смежности, как бы вы считали количество путей?

Answer 2

Возьмите A ^ n, затем прочитайте соответствующую запись.

Если вы хотите, чтобы это было более эффективно для одиночных вершин, выполните случайный обход, начиная с первой вершины для n итераций.

Answer 3

Как насчет использования алгоритма кратчайшего пути Дейкстры (DSPA)?Пусть стоимость каждой дуги в сети равна 1. Используйте DSPA, чтобы найти расстояние между двумя разными вершинами.Если длина равна n, вы нашли интересующий путь.Обведите все пары вершин.

Answer 4

Это мое кодирование, но я не знаю, как найти номер пути длины между двумя вершинами.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#define TRUE 1
#define FALSE 0

void main()
{
   int x;            
   int y;
   int n;
   int l;
   int a;
   int b;
   int length;
   char vertex='a';
   int num[50][50];

   printf("enter the number of vertices : ");
   scanf("%d",&n);
   //int num[n][n];

   for(x=0;x<n;x++)
   {
    for(y=0;y<n;y++)
      {
        printf("[%c,%c] : ",vertex+x,vertex+y);
         scanf("%d",&num[x][y]);
       }
   }

        printf("\n");

        printf("Adjacency matrix :\n");
        for(x=0;x<n;x++)
        {
            for(y=0;y<n;y++)

                printf("%d\t",num[x][y]);
                printf("\n");

            }

         printf("Enter a positive integer for length: ");
         scanf("%d",&length);

         length=sqrt(length);

         printf("Multiplication matrix :\n");
      for(l=0;l<=length;l++)
      {
        for(x=0;x<n;x++)
        {
            for(y=0;y<n;y++)

                num[x][y]=(num[x][y])*(num[y][x]);
               num[x][y]= num[x][y]+ num[y][x];

            }
       }


        printf("\n");

        for(x=0;x<n;x++)
        {
            for(y=0;y<n;y++)

                printf("%d\t",num[x][y]);
                printf("\n");

            }

         printf("\nPlease insert your starting point: ");
         scanf("%d",&a);
         printf("\nPlease insert your ending point: ");
         scanf("%d",&b);

         a=x-1;
         b=y-1;

         //printf("\nThe number of path from %d to %d: %d",a,b,num[a][b]);
         printf("\nThe number of path from %d to %d: %d",a,b,num[a][b]);

   getch();
   //return 0;

}