fork download
copy 
  1. /* dijkstra_grid.c
  2.    Dijkstra for a 7x7 grid graph (49 nodes).
  3.    The grid nodes are (r,c) with r,c in 0..6. Node id = r*7 + c.
  4.    Horizontal edges: between (r,c) and (r,c+1) -> hor[r][c], c=0..5
  5.    Vertical edges: between (r,c) and (r+1,c) -> ver[r][c], r=0..5
  6.  
  7.    NOTE: weights were transcribed by hand from the provided image:
  8.    /mnt/data/764ABF96-7B96-4B0D-8361-EC2D28F31024.jpeg
  9.    There may be small transcription errors. If you have a clearer image,
  10.    or want some weight adjusted, tell me and I'll update the arrays.
  11.  
  12.    Author: ChatGPT (educational example)
  13. */
  14.  
  15. #include <stdio.h>
  16. #include <limits.h>
  17.  
  18. #define NROWS 7
  19. #define NCOLS 7
  20. #define N (NROWS*NCOLS)
  21. #define INF 1000000000
  22.  
  23. int id(int r,int c){ return r*NCOLS + c; }
  24. void inv_id(int idx, int *r, int *c){ *r = idx / NCOLS; *c = idx % NCOLS; }
  25.  
  26. /* --- Transcribed weights from the image (best-effort) --- */
  27. /* hor[r][c] weight between (r,c) and (r,c+1), c=0..5 */
  28. int hor[NROWS][NCOLS-1] = {
  29.     /* row 0 */ {4, 4, 6, 7, 8, 2},
  30.     /* row 1 */ {5, 3, 2, 1, 1, 5},
  31.     /* row 2 */ {3, 4, 6, 7, 1, 2},
  32.     /* row 3 */ {2, 3, 1, 8, 3, 5},
  33.     /* row 4 */ {1, 2, 7, 3, 1, 1},
  34.     /* row 5 */ {3, 3, 4, 7, 7, 1},
  35.     /* row 6 */ {3, 3, 4, 7, 7, 1}
  36. };
  37. /* ver[r][c] weight between (r,c) and (r+1,c), r=0..5 */
  38. int ver[NROWS-1][NCOLS] = {
  39.     /* between row0 and row1 */ {4, 2, 1, 1, 1, 5, 1},
  40.     /* between row1 and row2 */ {3, 1, 1, 3, 7, 1, 2},
  41.     /* between row2 and row3 */ {8, 2, 7, 5, 3, 8, 8},
  42.     /* between row3 and row4 */ {4, 1, 2, 7, 3, 1, 1},
  43.     /* between row4 and row5 */ {3, 3, 3, 4, 7, 7, 2},
  44.     /* between row5 and row6 */ {1, 3, 1, 1, 1, 1, 1}
  45. };
  46.  
  47. /* Helper: check bounds */
  48. int in_bounds(int r,int c){ return r>=0 && r<NROWS && c>=0 && c<NCOLS; }
  49.  
  50. /* Dijkstra O(N^2) using adjacency generated on the fly */
  51. void dijkstra(int src, int target, int dist[], int parent[]) {
  52.     int used[N];
  53.     for(int i=0;i<N;i++){ dist[i]=INF; parent[i]=-1; used[i]=0; }
  54.     dist[src]=0;
  55.     for(int iter=0; iter<N; iter++){
  56.         int v=-1;
  57.         for(int i=0;i<N;i++) if(!used[i] && (v==-1 || dist[i] < dist[v])) v=i;
  58.         if(v==-1) break;
  59.         if(dist[v]==INF) break;
  60.         used[v]=1;
  61.         if(v==target) break;
  62.  
  63.         int vr, vc; inv_id(v,&vr,&vc);
  64.         /* try 4 neighbors */
  65.         int nr, nc, to, w;
  66.         /* left */
  67.         nr = vr; nc = vc-1;
  68.         if(in_bounds(nr,nc)){
  69.             to = id(nr,nc);
  70.             w = hor[vr][nc]; /* weight between (vr,nc) and (vr,vc) */
  71.             if(dist[v] + w < dist[to]){ dist[to] = dist[v] + w; parent[to] = v; }
  72.         }
  73.         /* right */
  74.         nr = vr; nc = vc+1;
  75.         if(in_bounds(nr,nc)){
  76.             to = id(nr,nc);
  77.             w = hor[vr][vc]; /* weight between (vr,vc) and (vr,vc+1) */
  78.             if(dist[v] + w < dist[to]){ dist[to] = dist[v] + w; parent[to] = v; }
  79.         }
  80.         /* up */
  81.         nr = vr-1; nc = vc;
  82.         if(in_bounds(nr,nc)){
  83.             to = id(nr,nc);
  84.             w = ver[nr][vc]; /* weight between (nr,vc) and (nr+1,vc) */
  85.             if(dist[v] + w < dist[to]){ dist[to] = dist[v] + w; parent[to] = v; }
  86.         }
  87.         /* down */
  88.         nr = vr+1; nc = vc;
  89.         if(in_bounds(nr,nc)){
  90.             to = id(nr,nc);
  91.             w = ver[vr][vc]; /* weight between (vr,vc) and (vr+1,vc) */
  92.             if(dist[v] + w < dist[to]){ dist[to] = dist[v] + w; parent[to] = v; }
  93.         }
  94.     }
  95. }
  96.  
  97. int main(){
  98.     int src = id(0,0);      /* V0 */
  99.     int target = id(6,6);   /* V* */
  100.     int dist[N], parent[N];
  101.     dijkstra(src,target,dist,parent);
  102.  
  103.     if(dist[target] >= INF){
  104.         printf("No path from source to target.\n");
  105.         return 0;
  106.     }
  107.  
  108.     printf("Shortest distance V0 -> V* = %d\n", dist[target]);
  109.     /* reconstruct path */
  110.     int path[N];
  111.     int len=0;
  112.     for(int v = target; v!=-1; v=parent[v]){
  113.         path[len++] = v;
  114.     }
  115.     printf("Path length (nodes): %d\n", len);
  116.     printf("Path (from source to target):\n");
  117.     for(int i=len-1;i>=0;i--){
  118.         int r,c; inv_id(path[i], &r, &c);
  119.         printf("  node %2d  (r=%d,c=%d)%s\n", path[i], r, c, (i==0?" <- source":""));
  120.     }
  121.  
  122.     /* also print path as coordinate sequence */
  123.     printf("Sequence of coordinates (r,c) from V0 to V*:\n");
  124.     for(int i=len-1;i>=0;i--){
  125.         int r,c; inv_id(path[i], &r, &c);
  126.         printf("(%d,%d)%s", r, c, (i>0 ? " -> " : "\n"));
  127.     }
  128.  
  129.     printf("\nNote: Weights were transcribed manually from the image. If you\nwant me to re-check any specific edge weight I will update arrays\nand re-run.\n");
  130.     printf("Image used for transcription: /mnt/data/764ABF96-7B96-4B0D-8361-EC2D28F31024.jpeg\n");
  131.  
  132.     return 0;
  133. }
  134.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Shortest distance V0 -> V* = 26
Path length (nodes): 15
Path (from source to target):
  node  0  (r=0,c=0)
  node  1  (r=0,c=1)
  node  8  (r=1,c=1)
  node  9  (r=1,c=2)
  node 10  (r=1,c=3)
  node 11  (r=1,c=4)
  node 12  (r=1,c=5)
  node 19  (r=2,c=5)
  node 18  (r=2,c=4)
  node 25  (r=3,c=4)
  node 26  (r=3,c=5)
  node 33  (r=4,c=5)
  node 34  (r=4,c=6)
  node 41  (r=5,c=6)
  node 48  (r=6,c=6) <- source
Sequence of coordinates (r,c) from V0 to V*:
(0,0) -> (0,1) -> (1,1) -> (1,2) -> (1,3) -> (1,4) -> (1,5) -> (2,5) -> (2,4) -> (3,4) -> (3,5) -> (4,5) -> (4,6) -> (5,6) -> (6,6)

Note: Weights were transcribed manually from the image. If you
want me to re-check any specific edge weight I will update arrays
and re-run.
Image used for transcription: /mnt/data/764ABF96-7B96-4B0D-8361-EC2D28F31024.jpeg
https://ideone.com/IPPxV5
language:
C (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!