#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INFINITY 9999
#define MAX 201
void dijkstra(int adjacencymatrix[MAX][MAX], int n, int startnode, int endnode)
{
      int cost[MAX][MAX], distance[MAX], pred[MAX];
      int visited[MAX], count, mindistance, nextnode, i, j;
      for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                  if (adjacencymatrix[i][j] == 0)
                        cost[i][j] = INFINITY;
                  else
                        cost[i][j] = adjacencymatrix[i][j];
      for (i = 1; i <= n; i++)
      {
            distance[i] = cost[startnode][i];
            pred[i] = startnode;
            visited[i] = 0;
      }
      distance[startnode] = 0;
      visited[startnode] = 1;
      count = 1;
      while (count < n - 1)
      {
            mindistance = INFINITY;
            for (i = 1; i <= n; i++)
                  if (distance[i] < mindistance && !visited[i])
                  {
                        mindistance = distance[i];
                        nextnode = i;
                  }
            visited[nextnode] = 1;
            for (i = 1; i <= n; i++)
                  if (!visited[i])
                        if (mindistance + cost[nextnode][i] < distance[i])
                        {
                              distance[i] = mindistance + cost[nextnode][i];
                              pred[i] = nextnode;
                        }
            count++;
      }
      for (i = 1; i <= n; i++)
      {
            if (i == endnode)
            {
                  printf("\nThe shortest distance between two nodes %d=%d", i, distance[i]);
                  printf("\nPath=%d", i);
                  j = i;
                  do
                  {
                        j = pred[j];
                        printf("<-%d", j);
                  } while (j != startnode);
            }
      }
}
int mapinput[201][201];
int adjacencymatrix[201][201];
int vertices;
int edge;
int u, y;
int main()
{
      int i, j;
      FILE *f = fopen("diamtest.txt", "r");
      if (f == NULL)
      {
            printf("FILE ERR\n");
            return 0;
      }
      else
      {
            fscanf(f, "%d %d", &vertices, &edge);
            for (i = 1; i <= vertices; i++)
            {
                  for (j = 1; j <= 2; j++)
                  {
                        fscanf(f, "%d", &mapinput[i][j]);
                  }
            }
      }
      for (i = 1; i <= vertices; i++)
            for (j = 1; j <= vertices; j++)
            {
                  if (mapinput[i][j] != i && j <= 2)
                  {
                        adjacencymatrix[i][mapinput[i][j]] = 1;
                        adjacencymatrix[mapinput[i][j]][i] = 1;
                  }
                  if (mapinput[i][j] == i && j <= 2)
                        adjacencymatrix[i][mapinput[i][j]] = 0;
            }
      printf("\nEnter the starting node:");
      scanf("%d", &u);
      printf("\nEnter the ending node:");
      scanf("%d", &y);
      dijkstra(adjacencymatrix, vertices, u, y);
      return 0;
}