Hello guys

under a project i have to complete for this semester i have to think and implement a shortest path algorithm other than the ones i have already coded so far for this course , which are:

- Bellman Ford

- Floyd

- Kruskal

The whole project is a bit weird because it says that i have to : make a "new" algorithm that computes the shortest path on a directed graph with positive weights on vertices and edges ,given in a txt file with this content (the graph i mean is this):

```
[15]
0 4 0 0 0 0 4 0 0 0 0 0 0 0 0
0 0 5 0 0 0 2 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 5 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 6 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 2 0 0 0 0
0 0 0 0 0 1 0 0 0 0 5 7 0 0 0
0 0 3 0 0 0 0 0 7 0 0 0 0 9 0
0 0 0 0 0 0 0 0 0 0 0 0 0 8 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 4 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
```

and the graph itself is this:

http://img152.imageshack.us/img152/1185/65843748il0.jpg

I can use any of the algorithms i already coded or a new one o can think of , as long as this time i also add not only the weights of the edges but the weight of each vertice as well.

The weights of the edges are these ones:

```
[15]
1 4 2 2 3 4 4 5 2 3 1 1 1 1 2
```

So now i have been thinking....what should i use to design a new shortest path algorithm that also counts the weights of the vertices and is based on some other already known shortest path algorithms ? (i hate re-inventing the wheel, i mean coding from scratch stuff already out there).

Just need some theoretical advice on this....would be grateful if you could share some ideas. Maybe also BFS or DFS could be used or A* ...dont know. Im open to suggestions.

Thanks in advance for your answers