java - Shortest Path LinkedList -

i want find shortest path on list of linked list, represents directed graph cost per edge/path.

the output this, tells me cost take me vertex 0 other vertices:

d[0 0] = 0 d[0 1] = 20 d[0 2] = 10 

this how populate list testing.

linkedlist<graphdata> g = new linkedlist[3];  (int = 0; < 3; i++)     weight[i] = new linkedlist<graphdata>();  g[0].add(new graphdata(1, 20); g[0].add(new graphdata(2, 10); 

the graphdata class looks this:

int vertex, int edgecost; 

now problem:

i want find shortest path vertex v others.

 public static int[] shortestpaths(int v, linkedlist<graphdata>[] cost) {     // set of vertices     int n = cost.length;      // dist[i] distance v     int[] dist = new int[n];      // s[i] true if there path v     boolean[] s = new boolean[n];      // initialize dist     for(int = 0; < n; i++)         dist[i] = cost[v].get(i).getcost();      s[v] = true;      // determine n-1 paths v      ( int j = 2 ; j < n  ; j++ )     {         // choose u such dist[u] minimal w s[w] = false         // , dist[u] < infinity         int u = -1;          (int k = 0; k < n; k++)             if ( !s[k] && dist[k] < infinity)                 // check if u needs updating                 if ( u < 0 || dist[k] < dist[u])                     u = k;         if (u < 0)             break;           // set s[u] true , update distances         s[u]=true;          (int k = 0; k < n; k++)             if ( !s[k] && cost[u].get(k).getcost() < infinity )                 if( dist[k] > dist[u] + cost[u].get(k).getcost())                     dist[k] = dist[u] + cost[u].get(k).getcost();          // @ point dist[k] smallest cost path         // v k of length j.     }            return dist; } 

this line dist[i] = cost[v].get(i).getcost(); throws "indexoutofboundsexception"

any idea doing wrong? appreciated.

there 2 common ways represent graphs: adjacency lists , adjacency matrices.

adjacency list: array of lists. element @ index i small list containing outgoing edges of vertex i. creating when populate list.

adjacency matrix: array of arrays, cost[i][j] containing cost of edge vertex i vertex j. using cost parameter if adjacency matrix.

you have 2 options:

• change graph construction create adjacency matrix , use array of arrays
• change algorithm treat cost adjacency list instead of adjacency matrix

here second option. renamed few things , simplified initialization first iteration calculates distance immediate neighbours of v (as opposed doing special case @ start).

import java.util.*;  public class main {     public static int[] shortestpaths(int v, linkedlist<edge>[] edges)     {         // set of vertices         int n = edges.length;          // dist[i] distance v         int[] dist = new int[n];         (int = 0; < n; i++) {             dist[i] = integer.max_value;         }          // seen[i] true if there path v         boolean[] seen = new boolean[n];          dist[v] = 0;          // determine n-1 paths v         (int j = 0; j < n; j++) {             // choose closest unseen vertex             int u = -1;              (int k = 0; k < n; k++) {                 if (!seen[k]) {                     // check if u needs updating                     if (u < 0 || dist[k] < dist[u]) {                         u = k;                     }                 }             }              if (u < 0 || dist[u] == integer.max_value) {                 break;             }              // @ point dist[u] cost of             // shortest path v u              // set seen[u] true , update distances             seen[u] = true;              (edge e : edges[u]) {                 int nbr = e.gettarget();                 int altdist = dist[u] + e.getcost();                 dist[nbr] = math.min(dist[nbr], altdist);             }         }          return dist;     }      public static void main(string[] args)     {         int n = 5;         int start = 0;         linkedlist<edge>[] cost = new linkedlist[n];         (int = 0; < n; i++) {             cost[i] = new linkedlist<edge>();         }          cost[0].add(new edge(1, 20));         cost[0].add(new edge(2, 10));         cost[1].add(new edge(3, 5));         cost[2].add(new edge(1, 6));          int[] d = shortestpaths(start, cost);         (int = 0; < n; i++) {             system.out.print("d[" + start + " " + + "] = ");             system.out.println(d[i]);         }     } }  class edge {     int target, cost;      public edge(int target, int cost) {         this.target = target;         this.cost = cost;     }      public int gettarget() {         return target;     }      public int getcost() {         return cost;     } }