•

Check out our Community Blogs

Register and join over 40,000 other developers!

### Recent Blog Entries

• phi

I love this community !

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

Shortest Path Dijkstra Directed Graph shortest path

3 replies to this topic

### #1 kernelcoder

kernelcoder

CC Devotee

• Expert Member
• 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

Programming God

• Senior Member
• 897 posts
• 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
• 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
• 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