Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Shortest Path In A Weighted Directed Graph With Dijkstra's Algorithm

Shortest Path Dijkstra Directed Graph shortest path

  • Please log in to reply
3 replies to this topic

#1 kernelcoder

kernelcoder

    CC Devotee

  • Expert Member
  • PipPipPipPipPipPip
  • 990 posts
  • Location:Dhaka
  • Programming Language:C, Java, C++, C#, Visual Basic .NET
  • Learning:Objective-C, PHP, Python, Delphi/Object Pascal

Posted 28 May 2012 - 09:48 AM

Well, I encountered an interesting problem. I was asked to solve the "Shortest Path" problem using Dijkstra's Algorithm but I was forbidden to use linked-list and any fixed size array (e.g. int var[10] ;). You guys don't need to write code for the problem but just can post your thoughts. I know there are more than one ways to solve a problem and that's why asking for the solutions from you so that I can learn the other ways.



Here is an input of a graph. I wrote it from the above wiki link example.

Number of vertix ( less than 10000): 6
Number of Edges: 18
Maximum total length will not exceed 100000000.

Edges:


Weight Source Dest
14 0 5
14 5 0
7 0 1
7 1 0
9 0 2
9 2 0
10 1 2
10 2 1
15 1 3
15 3 1
2 2 5
2 5 2
11 2 3
11 3 2
9 5 4
9 4 5
6 3 4
6 4 3
  • 0

#2 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 29 May 2012 - 05:05 AM

Can you use a dynamic array.
  • 0

#3 kernelcoder

kernelcoder

    CC Devotee

  • Expert Member
  • PipPipPipPipPipPip
  • 990 posts
  • Location:Dhaka
  • Programming Language:C, Java, C++, C#, Visual Basic .NET
  • Learning:Objective-C, PHP, Python, Delphi/Object Pascal

Posted 31 May 2012 - 11:24 PM

Yes, you can. But tell us about the data-structure for graph.
  • 0

#4 kernelcoder

kernelcoder

    CC Devotee

  • Expert Member
  • PipPipPipPipPipPip
  • 990 posts
  • Location:Dhaka
  • Programming Language:C, Java, C++, C#, Visual Basic .NET
  • Learning:Objective-C, PHP, Python, Delphi/Object Pascal

Posted 01 June 2012 - 12:46 AM

To solved it I used the following structure.

struct __Edge__ {
int to_vertex;
unsigned long weight;
};
typedef struct __Edge__ Edge;

struct __Vertex__ {
int edgeCount;
Edge* edge;
};
typedef struct __Vertex__ Vertex;

Then I used following code to create the graph data-structure.
Vertex* graph;
int i;
int source,  dest;
int vertexCount;
unsigned long edgeCount, weight;

scanf("%d %lu", &vertexCount, &edgeCount);

/* Allocate memory for vertexes */
graph= (Vertex*)malloc(vertexCount * sizeof(Vertex));
memset((void*)graph, 0, vertexCount * sizeof(Vertex)); /* init with 0 */

/* Allocate & create the edges */

for(i = 0; i < edgeCount; i++) {
scanf("%lu %d %d", &weight, &source, &dest); 
graph[source].edge = realloc((void*)(graph[source].edge), (graph[source].edgeCount + 1) * sizeof(Edge));
graph[source].edge[g[source].edgeCount].weight = weight;
graph[source].edge[g[source].edgeCount].to_vertex = dest;
graph[source].edgeCount++;
}
So, the solution was to use the malloc & realloc C standard library functions to allocate memory to not to use the linked list. And then I call the Dijkstra algorithm on the graph.
  • 0





Also tagged with one or more of these keywords: Shortest Path, Dijkstra, Directed Graph, shortest path

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download